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

참고 사이트

https://yabmoons.tistory.com/364

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

 

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

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

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

 

방문하는 순서는 BFS와 같다

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

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

 

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

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

 

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

 

SSS