Shortest-Path  Algorithm

이산수학 : Richard Johnsonbaugh 저서, 강홍식.김정인.이도훈.이명재 번역, 교보문고, 1999 (원서 : Discrete Mathematics 6th ed, Prentice-Hall, 1997), Page 402~409

가중치 그래프가 간선에 값을 부여한 그래프이고, 가중치 그래프 내의 경로의 길이는 경로 안의 간선의 가중치의 합이라는 것을 상기하자 (서론 참조). 간선 의 가중치를 로 표기한다. 가중치 그래프에서, 두개의 주어진 정점 간의 최단 경로 (shortest path) (즉, 경로가 최소 길이를 갖는다) 를 찾기를 종종 원할 때가 있다. 다익스트라 (E.W. Dijstra) 에 의한 Algorithms 6.4.1 이, 문제를 효율적으로 해결하는데, 이 절에서 다룰 과제이다.

다익스트라 (Edsger W. Dijkstra : 1930-) 는 네덜란드에서 태어났다. 그는 일찍이 과학으로서 프로그래밍을 창시한 사람이였다. 프로그래밍에 매우 열성이었던 그는 1957년 결혼을 했을 때, 프로그래머로서의 명성이나 있었다. 하지만 독일 당국은 그 같은 전문성을 인정하지 않았기 때문에 단지 "이론 물리학자" 라고 바꾸어 기입해야 했다. 그러나 1972년에 ACM 으로부터 그 유명한 튜링상을 수상했다. 그는 또한 1984년에 오스틴에 있는 텍사스 대학에 전산학과에 Schlumberger Centennial Chair 에 임명되었다. 이 절을 통하여, G 는 연결되고 가중치 그래프를 나타낸다. 가중치는 양수이고 어떤 정점 a 에서 정점 z 로의 가장 짧은 경로를 찾고자 한다. G 가 연결되었다는 가정은 생략될 수도 있다 (연습 문제 9를 보라).

다익스트라의 알고리즘은 정점에 표시하는 문제까지 포함된다. 정점의 표시라고 하자. 어떤 점에서, 어떤 정점들은 임시적인 표시를 하고 또 어떤 것들은 확정적인 표시를 한다. T 를 임시적인 표시를 가지는 정점들의 집합이라고 하자. 알고리즘을 설명함에 있어, 확정적인 값을 가지는 정점들은 동그라미를 할 것이다. 가 정점 v 의 확정적인 값이라면, 는 a 에서 v 로 가는 최단 경로 길이다. 최초에 모든 정점들은 임시 값을 가질 것이다. 알고리즘이 반복될 때마다, 그 값들이 임시적인 것에서 확정적인 것으로 바뀔 것이다 ; 따라서 이 알고리즘은 z 가 확정적인 값이 되었을 때 종료하게 된다. 이때, 는 a 에서 z 로의 최단 경로의 길이가 된다.

 (알고리즘 4.1)   다익스트라의 최단 경로 알고리즘

이 알고리즘은 연결된 가중치 그래프에서 정점 a 에서 정점 z 로의 최단 경로의 길이를 찾는 것이다. 간선 의 가중치는 이고 정점 x 의 값은 이다. 마지막에, , a 에서 z 까지의 최단 경로 길이.

1.    procedure
2.         
3.            for 모든 정점 do
4.                
5.            T := 모든 정점의 집합
6.            // T 는 a 로부터 최단 거리 계산을 위해 아직 방문하지
7.            // 않은 정점의 집합
8.            while do
9.                begin
10.              최소 를 가지는 을 선택
11.              T := T-{v}
12.              for v 에 인접한 각 do
13.                 := min
14.              end
15.  end

(예제 4.2)  

알고리즘 4.1 이 그림 1 의 그래프에서 a 에서 z 로의 최단 경로를 어떻게 찾는지 보자 (T 의 정점들은 동그라미를 하지 않았고 임시적인 값을 가지고 있다. 동그라미로 된 정점은 영구적인 값을 가진다). 그림 2 는 줄 2-5 를 실행한 결과를 보이고 있다. 8번에서 z 는 동그라미를 하지 않았다. 10번까지 실행하면, 가장 작은 값을 가진 동그라미가 안 된 정점 a 를 선택하여 동그라미를 한다 (그림 3 을 보라). 12 와 13 번 줄에서 동그라미가 안 되어 있고, a 에 인접하는 정점 b 와 f 를 변경한다. 따라서 다음과 같이 새로운 값을 구할 수 있다.

           

(그림 2 를 보라). 여기서 8 번으로 돌아간다.

그림 1  예제 4.2 를 위한 그래프

그림 2  다익스트라 최단 경로 알고리즘에서 초기화

z 가 동그라미가 안되었기 때문에, 10 번까지 실행한다. 이때, 동그라미 안 된 가장 작은 값을 가지는 정점 f 를 선택하여 동그라미를 한다 (그림 4 를 보라). 12 와 13 번 줄에서 정점 f 에 인접하고 동그라미가 안 된 정점 d 와 g 의 값을 변경한다. 그림 4 가 그 결과를 보여 주고 있다.

그림 3  다익스트라의 최단 경로 알고리즘의 첫 번째 반복

그림 4  다익스트라의 최단 경로 알고리즘의 두 번째 반복

알고리즘의 다음 반복의 그림 5 에서 보여주는 값들을 만들어낸다는 것을 보여주고, 알고리즘의 종료가 z 에서 5 의 값을 가질 때 일어나는 것을 보여야 한다. 물론 이때의 5 는 a 에서 z 로의 최단 경로의 길이를 의미한다. 최단 경로는 (a, b, c, z) 이다.

그림 5  다익스트라의 최단 경로 알고리즘의 세 번째 반복

다음은 알고리즘 4.1 이 참임을 보인다. 증명은 다익스트라의 알고리즘은 a 로부터 오름차순으로 최단 경로의 길이를 찾는다는 사실에 근간을 두고 있다.

 (정리 4.3)  

다익스트라의 최단 경로 알고리즘 (알고리즘 4.1) 은 a 에서 z 로의 최단 경로 길이를 정확하게 찾는다.

증명   번 실행으로 10 번에 도달할 수 있음을 증명하기 위해 에 대한 수학적 귀납법을 사용한다. 는 a 에서 v 로의 최단 경로 길이를 말한다. 이것이 증명될 때, z 가 10 번에서 선택되기 때문에 알고리즘의 정확성이 밝혀지며, 는 a 에서 v 로의 최단 경로 길이가 된다.

기본 단계  10 번 줄에 도착하는 첫 번째, 초기화 단계 (2-4 번 줄) 이기 때문에, 는 0 이고 나머지는 모두 ∞ 이다. 따라서 10 번 줄에 도착했을 때 처음으로 a 를 선택한다. 가 0 이므로, 는 a 에서 a 로의 최단 경로 길이이다.

귀납 단계   에 대해, 번째 10 번에 도착했을 때, 는 a 에서 v 로의 최단 경로 길이이다.

번째 10번에 도착했을 때, T 안에 있는 최소값 을 가지는 v 를 선택한다고 가정한다.

먼저 보다 작은 값을 갖는 a 에서 w 로의 경로가 있다면 w 는 T 안에 존재하지 않는다 (즉, w 는 10 번 줄 이전에 선택되었다) 는 것을 보인다. w 가 T 안의 정점이라고 모순된 가정을 하자. P 를 a 에서 w 로의 최단 경로라 하고, x 는 T 안에 있으면서 P 상의 a 에 가장 가까운 정점이라 하자. 그리고 u 를 P 상의 x 의 앞선 정점이라 하자 (그림 6 를 보라). 그러면 u 는 T 안의 정점이 아니다. 따라서 u 는 while 루프의 이전 반복과정에서 10번 줄에서 선택되었다. 귀납 과정에 의해 는 a 에서 u 로의 최단 경로의 길이이다. 다음의 결과를 얻을 수 있다.



그러나 이 부등식은 v 는 최소값 를 가지는 T 안의 정점이 아님을 보여 준다 [ 는 더 작다]. a 에서 어떤 정점 w 의 경로가 존재하고 그 길이가 보다 작으면, w 는 T 안에 있지 않다는 것을 위의 모순에 의해 증명할 수 있다.

그림 6  정리 4.3 의 증명. P 는 a 에서 w 까지의 최단 경로이고, x 는 T 에 있는 P 상의 a 에 가장 근접한 정점이다. 그리고 u 는 P 에서 x 의 선행자이다.

앞선 결과는 특히 a 에서 v 로의 경로가 존재하고 그 길이가 보다 작으면 v 는 10번 줄 이전에 벌써 선택되어지고 T 에서 제거되어 있다는 사실을 알 수 있다. 그러므로 a 에서 v 로의 모든 경로는 적어도 의 길이를 가진다. 가설에 의해 a 에서 v 로의 경로 길이 가 존재하고, 이는 a 에서 v 까지의 최단 경로이다. 이것으로 증명이 끝났다.

알고리즘 4.1 은 a 에서 z 로의 최단 경로 길이를 구한다. 대부분의 응요에서, 최단 경로를 확인하고 싶어한다. 알고리즘 4.1 을 약간 수정하면 최단 경로를 구하는 문제를 거의 해결할 수 있다.

 (예제 4.4)  

그림 7 의 그래프에서 a 에서 z 까지의 최단 경로와 그 길이를 구하라.

알고리즘 4.1 을 약간 수정하여 적용할 것이다. 정점에 동그라미를 하는 것 외에, 어떤 정점으로부터 왔는지를 알 수 있는 꼬리표를 함께 표시한다.

그림 7 은 알고리즘 4.1 의 2-4 번 줄을 수행하고 난 다음의 결과를 보여주고 있다. 먼저 a 를 동그라미를 한다 (그림 8 를 보라). 다음으로 a 에 인접한 b 와 d 에 표시를 한다. 정점 b 에는 그 값과 a 로부터 파생되었음을 나타내는 "a, 2" 라는 표시를 한다. 마찬가지로, 정점 d 에는 "a, 1" 이라고 표시한다.

그림 7  다익스트라의 최단 경로 알고리즘의 초기화

그림 8  다익스트라의 최단 경로 알고리즘의 첫 번째 반복

그 다음으로 정점 d 에 동그라미를 하고 d 의 인접한 정점 e 에 표시를 한다 (그림 9 를 보라). 그런 다음, 정점 b 에 동그라미를 하고 c 와 e 에 표시를 수정한다 (그림 10 을 보라). 그 다음, 정점 e 에 동그라미를 하고 정점 z 의 표시를 수정한다 (그림 11 를 보라). 여기서 z 에 동그라미를 하고, 알고리즘은 종료될 것이다. a 에서 z 까지의 최단 경로의 길이는 4 이다. z 에서 출발하여, 다음 경로를 구할 수 있는 표시를 다시 따라갈 수 있다.

(a, d, e, z)

그림 9  다익스트라의 최단 경로 알고리즘의 두 번째 반복

그림 10  다익스트라의 최단 경로 알고리즘의 세 번째 반복

다음 정리는 다익스트라 알고리즘이 최악의 경우 임을 보여 준다.

그림 11  다익스트라의 최단 경로 알고리즘의 결론

 (정리 4.5)  

개의 정점으로 구성되고, 단순, 연결된 가중치 그래프에 대하여, 다익스트라의 알고리즘 (알고리즘 4.1) 은 최악의 경우 실행 시간을 가진다.

증명  루프 안에서 전체 시간의 상한을 제공하는 시간 소요를 고려하자. 4 번째 줄의 실행 시간은 이다. while 루프 안에서, 10 번은 시간이 소요된다 (최소 을 T 안에 있는 모든 정점을 조사하여 찾을 수 있다). for 루프 (13 번) 의 몸체는 실행 시간이 소요된다. 10-13 번 줄은 의 시간이 소요되나 while 루프에 내포된 관계로, 전체적으로 소요되는 시간은 이다. 그래서 다익스트라의 알고리즘은 의 실행 시간이 걸린다.

사실, z 의 적절한 선택을 위해 소요되는 시간은 개의 정점을 가지는 완전 그래프 에 대해 이다. 그 이유는 모든 정점이 다른 모든 정점에 인접해 있기 때문이다. 따라서 최악의 경우 실행 시간은 이다.

개의 정점을 가지는 완전 그래프 을 입력으로 받는 어떤 최단 경로 알고리즘도 의 모든 간선을 적어도 한 번 검사해야 한다. 이 개의 간선을 가지므로 (서론의 연습 문제 11 을 보라), 최악의 경우 실행 시간은 적어도 이어야 한다. 정리 4.5 로부터 알고리즘 4.1 이 최적임을 알 수 있다.