다익스트라 알고리즘

1. 시작한 곳을 dist를 0으로 잡고 시작. 거리비용들의초기값은 INF로 한다.

2. 우선순위 큐를 사용하여 거리비용이 낮은 순으로 탐색

3. 조건은 현재노드에 있는 다음 노드들, 즉 붙어 있는 노드들을 탐색

4. 그 노드들에 대해서 dist보다 현재 노드와 붙어 있는 노드로 가는 거리비용을 합한 값이 작을 경우 값을 적는다.

5. 다음 우선순위 큐가 없을 때까지 반복하면 모든 곳을 최소비용으로 순회하게 된다.

6. 시작지점부터 도착지점까지 최소 비용을 구하는 문제에 사용.

 

 

도움 사이트 : yabmoons.tistory.com/364

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