다엑스트라 알고리즘

다엑스트라 알고리즘이란 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 알고리즘이다.

다엑스트라 알고리즘은 가중치가 음수인 그래프에서 사용못한다.

다익스트라 알고리즘은 너비우선탐색(BFS)을 기반으로 한다.

작동 과정

1. 시작 노드외 나머지 노드들의 거리를 무한대(∞)로 초기화시킨다.

2. 시작 노드와 이웃한 노드들의 가중치를 저장한다.

3. 방문하지 않는 노드들 중에서 가장 가중치가 낮은 노드를 선택한다.

4. 해당 노드를 거쳐서 방문하지 않는 노드들로 가는 경우를 고려하여 최소 가중치를 갱신한다.

5. 모든 노드들을 방문할때까지 3,4를 반복한다.