WinCNT

경로 탐색 알고리즘 - 다익스트라 (Dijkstra) 본문

게임 프로그래밍(학습 내용 정리)/자료구조와 알고리즘

경로 탐색 알고리즘 - 다익스트라 (Dijkstra)

WinCNT_SSS 2022. 1. 18. 14:45

참고 사이트

https://yabmoons.tistory.com/364

 

[ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)

그래프 알고리즘에서 '최소 비용'을 구해야 하는 경우 사용할 수 있는 대표적인 알고리즘으로는 '다익스트라 알고리즘' , '벨만-포드 알고리즘' , ' 플로이드 워샬 알고리즘' 이 있다. 이번 글에서

yabmoons.tistory.com

 

다익스트라 (Dijkstra) 알고리즘

출발 정점부터 각 정점까지의 거리(비용)을 계산한 테이블이 필요하다

초기값은 무한대(...)나 음수를 두면 된다

 

방문하는 순서는 BFS와 같다

하지만 다익스트라는 큐가 아니라 우선순위 큐를 사용한다

(비용이 적은 노드를 먼저 뽑을 수 있게)

 

또한 방문한 노드나 그리드의 경로의 최소 비용을 알고 있는 테이블 등도 필요하다

(경로의 최소 비용당 갱신함)

 

내비게이션 시스템, NavMesh 등에 자주 사용된다

 

SSS

'게임 프로그래밍(학습 내용 정리) > 자료구조와 알고리즘' 카테고리의 다른 글

경로 탐색 알고리즘 - A*  (0) 2022.01.25
경로 탐색 알고리즘 - 너비 우선 탐색(BFS, Breadth First Search)  (0) 2022.01.18
자료 구조에 대해서(보충)  (0) 2022.01.18
자료구조 - 그래프  (0) 2022.01.17
메모리 정렬  (0) 2022.01.11
'게임 프로그래밍(학습 내용 정리)/자료구조와 알고리즘' Related Articles more