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

최단경로를 구하는 알고리즘인 다익스트라 알고리즘을 공부하고자 한다.

다익스트라 알고리즘은 한 점에서 모든 점까지 최단거리를 구하는 알고리즘인데, 가중치가 양수일 때만 사용하는 알고리즘이다.

예시에서는 1에서 7까지 도달하는 최단경로를 구한다고 해보자.

먼저 시작정점 1까지는 최단경로 0으로 왔기 때문에 최단경로 0으로 도착했다고 표시한다.

그리고 다음 경로로 2와 6으로 갈 수 있는데, 1에서 6으로 가는 방법은

1 --> 6 과 1 --> 2 --> 6 두가지가 있다.

1에서 2로 가는 방법은 1 --> 6 --> 2 와 1 --> 2 가 있다.

1 --> 2 --> 6 과 1 --> 6 --> 2 를 구하려면

2 --> 6 과 6 --> 2 를 알아야 하는데, 아직 1 --> 6 로 갈지 1 --> 2 로 갈지

정하지 않았기 때문에 정할 수 없는 딜레마에 빠진다. 한 점에서 모든 점까지 가는 최단경로를 구하여야 하기 때문이다.

예를들어 1에서 6으로 가는 최단경로를 구할 때 봐야하는 곳은

1 --> 6 으로 가는 것과 2 --> 6 으로 가는 것을 봐야하는데,

1 --> 6 으로 가는 가중치 1보다 2 --> 6 으로 가는 가중치가 더 작아질 수 있을까?

답은 작아질 수 없다. 왜냐하면 1에서 6으로 가는 2번째 방법인 1 --> 2 --> 6 은 2를 거쳐가기 때문에

1 --> 2 의 가중치가 3이라 절대 1보다 작아질 수 없기 때문이다. 그래서 6까지 가는 최단경로는 1 --> 6 으로 확정할 수 있다.

다음으로 2까지 가는 최단경로를 구하면 2가지가 있는데, 1 --> 6 --> 2와 1 --> 2가 있다.

각각의 값은 2 와 3 이기 때문에 6을 거쳐 2를 가는것이 최단경로라고 확정 할 수 있다.

이제 2에서 다음 경로 3과 4로 가는 최단경로를 정해야 한다. 4로가는 경로는 2 --> 4와 5 --> 4가 있고,

3으로 가는 경로는 2 --> 3, 5 --> 3, 7 --> 3, 8 --> 3 이 있다.

2 --> 3 과 2 --> 4 빼고 나머지는 아직 경로 확정이 안되었기 때문에, 구할수가 없다.

그래서 2 --> 3으로가는 경로는 8이고, 2 --> 4로가는 경로는 5라는 것을 알 수 있다.

둘중에 더 작은 값인 2 --> 4로 가는 경로 5를 최단거리로 확정한다.

이제 4까지 가는 최단경로를 구했으므로, 이제 4에서 가는 경로를 구해야 한다.

4에서 가는 경로는 5밖에 없으므로 4 --> 5의 경로 가중치의합인 5를 최단경로로 확정한다.

그리고 나서 5에서 갈 수 있는 5 --> 3, 5 --> 7 과 2 --> 3을 봐야한다.

3으로 가는 최단경로는 5 --> 7, 5 --> 3 보다 2 --> 3 이 8로 더 짧으므로

3까지 가는 경로를 확정한다.

이제 3 --> 8, 3 --> 7 과 5 --> 7 을 비교한다. 3 --> 8 이 10으로 가장 짧으므로

3 --> 8 로 8 까지 가는 경로를 확정하고, 마지막으로

8 --> 7 : 12      /       3 --> 7  : 15         /       5  --> 7 : 14

중에 가장 작은 값인 8 --> 7을 최단경로로 확정한다.

최단경로만 그래프에서 표시해보면 트리모양이 되는데, 트리는 사이클이 없는 그래프라고 정의할 수 있다.

그러므로 다익스트라알고리즘을 이용하여 최단경로를 구하면 최단경로 트리가 된다.

---

이제 최단경로 트리를 만드는 법을 알아보자. T(i) 를 i까지 도달하는 최단거리로 정의한다.

시작하는 점 1은 최단거리 0으로 도착했다고 표시한다.

1 --> 6은 최단거리가 1이므로 6에 1을 저장하고, 도착했다고 표시한다.

1 --> 2는 최단거리가 3이므로 3만 저장한다.

2 까지 도달하는 최단거리는 1 --> 6 --> 2 이므로 2의 최단거리를 3에서 2로바꾸고

도착했다고 표시한다. 그리고 2에서 3과 4로 갈 수 있는 방법이 두가지 있다.

2 --> 3까지 최단거리는 6이므로 3에 6을 저장하고 4는 3이므로 4에 3을 저장한다.

3이 최단거리이므로 4에 도착표시를 한다. 그리고 5는 3에서 2를 더한 5의 값이 최단거리이므로

5를 저장하고 도착했다고 표시한다.

5에서 3에 갈 수 있는 방법은 11인데, 3에 이미 2 --> 3으로 가는 방법에 최단거리인 6이 저장되어 있다.

5 --> 7 로 가는 거리는 14이므로 7에 14를 저장한다.

3으로 가는 최단거리는 2를 통해 가는 방법이 최단거리이기 때문에 3에 표시를 한다.

이제 3에서 8에 갈 수 있는 거리인 10을 8에 저장하고, 3 --> 7 의 방법은 15인데

5 --> 7 의 방법인 14가 더 작기 때문에 7에는 여전히 14가 저장되어 있다.

3을 통해 8에가는 방법이 최단거리이기 때문에 8에 도착표시를 하고,

이제 마지막으로 7까지 가는 방법을 봐야하는데, 8을 통해 7에 오는 거리가 13이기 때문에

7에 13을 저장하고 7에 도착표시를 하면 최단경로 트리가 완성된다

출처 : Algorithm LABS