다익스트라(Dijkstra) 알고리즘 ( 최단거리 찾기 알고리즘 )

[point]

해당 노드에서 직접 바라보는 부모노드와의 거리보다 다른 연결로 들어온 경로의 거리가 더 적다면

적은 거리로 온 노드를 부모로 바라본다

---

시작 A

모든 노드는 A 를 가르키고 (parent)

직접 가르키지 못하는 노드들은 무한대로 거리를 설정한다

1.A 를 처음 방문하고 방문하지 않은 최소 비용으로 연결된 노드에 대해서 탐색을 시작한다

2. 그래서 처음 C 를 방문하게 된다

(노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 )

3. C 를 살펴보면 C 는 D 와 연결 되어 있고 D 는 A 를 가르키고 있다

그런데 A에서 C 그리고 C 에서 D 로 가는 비용이 3 이고 A 에서 D 로 가는 비용이 2 총 3 이기 때문에

D 가 더 빨라 D 가 가르키는 부모와 distance를 바꾸지 않아도 된다

[반복..] 인접한 것과 방문은 다른 것

4. 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 (D)

5. D 와 인접한 G 와 F 노드가 있는데

먼저 F 를 보면 F의 비용은 무한대 이기 때문에 D 에서 F 로 누적된 6 만큼 이동 하는 것이 더 빠르기 때문에

(F A 무한대) 를 (F D 6) 으로 바꿔준다

G 도 무한대 비용인데, D 에서 G 로 가는 누적된 6 이 더 작음으로

(G A 6) 을 ( G D 6 ) 으로 바꿔준다 (이렇게 parent 를 세팅해나간다)

6. 다시 노드를 방문하지 않은 것중에 distance 가 적은 것의 노드를 방문한다 이번에는 (E) 가 선택 된다

반복...

결과

최종적으로 Vertex 가 바라보는 Parent 로 연결되는 선을 연결해주면 위 그림처럼 나오고

최단 경로는 시작점 A 에서부터 모든 점에 대한 최단 거리를 연결해 놓은 형태가 됨으로

A 가 아닌 어떤 노드에서 부모를 따라 가면 어떤노드에서 A 까지 가는 최단 경로가 나온다