데이크스트라 알고리즘

역사

로테르담에서 흐로닝언까지, 일반적으로 한 도시에서 다른 도시로 가는 가장 짧은 길은 무엇일까요? 이것은 제가 이십 분 동안 생각해낸 최단 거리를 찾는 알고리즘입니다. 어느 날 아침에 저는 제 약혼녀와 암스테르담에서 쇼핑을 하고 있었고, 지쳤었기 때문에 카페 테라스에 앉아서 커피를 마시면서 그 문제에 대해서 생각하다가 최단 거리를 찾는 알고리즘을 고안했습니다. 제가 말했듯이, 이것은 이십 분 짜리 발명품입니다. 사실, 이 알고리즘은 삼 년 뒤인 59년에 발표했습니다. 그 간행물을 여전히 읽을 수 있습니다. 사실은 꽤 괜찮습니다. 이것이 괜찮은 이유 중 하나는 제가 이 알고리즘을 고안할 때 연필과 종이 없이 고안했다는 것입니다. 제가 나중에 알게 된 바로는 연필과 종이 없이 고안하는 것의 좋은 점은 고안 할 때 피할 수 있는 복잡성을 피하도록 거의 강요되기 때문이라고 합니다. 갑자기 그 알고리즘이 나타남이 저를 놀랍게 했으며 제 명성의 초석이 되었습니다.
— 에츠허르 데이크스트라, Philip L과의 인터뷰에서. Frana, Communications of the ACM, 2001
데이크스트라는 1956년에 네덜란드 국립 수학 정보과학 연구소에서 새로운 컴퓨터 ARMAC의 수용력을 입증하는 프로그래머로 일할 때 최단 경로 문제에 대해서 생각했다. 이제 해야 할 일은 컴퓨터를 다루지 않는 사람들도 이해할 수 있도록 문제와 (컴퓨터가 만들어낸)해법을 둘 다 선택하는 것이었다. 그는 최단 거리 알고리즘을 고안하고, 이후 ARMAC에서 약간 단순화된 네덜란드 도시 64개(도시의 숫자를 표시하기 위해서 6 비트만 필요하도록 64를 선정했다)의 교통 지도에 대해서 수행했다. 일 년 뒤, 데이크스트라는 기관의 다음 컴퓨터를 작업하던 하드웨어 엔지니어들의 문제를 직면했다: 기계의 후면 패널에 있는 핀을 연결 할 때 필요한 전선의 개수를 최소화 하는 것이다. 그 해법으로, 프림 최소 신장 트리 알고리즘으로 알려진 알고리즘을 재발견 했다(이전에는 Jarník에 의해 알려져 있었고, 또한 프림에 의해 재발견 되었었다). 데이크스트라는 이 알고리즘을 프림이 발표한 지 2년 뒤이고 Jarník이 발표한 지 29년 뒤인 1959년에 발표했다.

의사 코드

다음 알고리즘에서, 코드 u ← vertex in Q with min dist[u]는 꼭짓점 집합 Q에서 가장 작은 dist[u] 값을 가지는 꼭짓점 u를 찾는다. length(u, v)는 두 인접한 꼭짓점인 u와 v를 연결하는 변의 길이 (둘 간의 거리)를 반환한다. 18번째 줄의 변수 alt는 루트 꼭짓점에서 u를 통해서 인접 꼭짓점 v까지 가는 경로의 길이이다. 이 경로가 현재 v에 대해서 기록된 최단 경로보다 짧다면, 현재 경로를 이 alt 경로로 대체한다. prev 배열은 소스까지 최단 경로를 찾기 위한 소스 그래프의 "다음" 꼭짓점을 나타내는 배열이다.
 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // 초기화
 6          dist[v] ← INFINITY                           // 소스에서 v까지의 아직 모르는 길이
 7          prev[v] ← UNDEFINED                          // 소스에서 최적 경로의 이전 꼭짓점
 8          add v to Q                                // 모든 노드는 초기에 Q에 속해있다 (미방문 집합)
 9
10      dist[source] ← 0                                 // 소스에서 소스까지의 길이
11
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]         // 최소 거리를 갖는 꼭짓점
14                                                            // 을 가장 먼저 선택한다
15          remove u from Q
16
17          for each neighbor v of u:           // v는 여전히 Q에 있다.
18              alt ← dist[u] + length(u, v)
19              if alt < dist[v]:               // v 까지의 더 짧은 경로를 찾았을 때
20                  dist[v] ← alt
21                  prev[v] ← u
22
23      return dist[], prev[]
만약 source에서 target까지의 최단 경로만을 구하고 싶다면, 15번째 줄에 u = target을 추가해서 종료시킬 수 있다.
그리고 나서는 source에서 target까지의 최단 경로를 역방향 반복을 통해서 읽을 수 있다:
1  S ← empty sequence
2  u ← target
3  while prev[u] is defined:                // 스택 S로 최단 경로를 만든다
4      insert u at the beginning of S         // 꼭짓점을 스택에 넣는다
5      u ← prev[u]                           // target에서 source로 이동한다
6  insert u at the beginning of S             // source를 스택에 넣는다
그러면 수열 S는 source에서 target으로 가는 경로에 있는 꼭짓점의 목록이거나 경로가 존재하지 않다면 빈 수열이다.
더 일반적인 문제는 source에서 target까지 가는 모든 최단 경로를 찾는 것이다(같은 길이를 가지는 다른 경로가 있을 수 있다). 그러면, 각각의 prev[]에 꼭짓점 하나만을 저장하는 것이 아니라, 경감 조건을 만족하는 모든 꼭짓점을 모두 저장할 수 있다. 예를 들어, r과 source가 둘 다 target으로 연결되어 있고 (변의 비용이 두 경우 모두 다 같아서) 둘 다 target으로 가는 다른 최단 경로에 있다면, prev[target]에 r과 source 모두 추가해야 한다. 알고리즘이 끝나면, prev[]의 자료구조는 원래 그래프의 일부 변이 제거된 부분 집합을 나타낼 것이다. 이 자료구조의 가장 중요한 특성은 알고리즘의 시작점이 여러 개였을 때, 새 그래프에서 그 꼭짓점에서 다른 꼭짓점으로 가는 모든 경로가 원래 그래프의 그 꼭짓점에서도 최단 경로라는 점과, 원본 그래프에서 그 길이를 가지는 모든 경로가 새로운 그래프에도 나타난다는 점이다. 실제로 주어진 두 꼭짓점 간의 최단 거리를 모두 찾기 위해서는 새로운 그래프에서 깊이 우선 탐색 같은 경로 찾기 알고리즘이 필요하다.

우선순위 큐 사용

최소 우선 큐는 다음의 세 기본 연산을 제공하는 추상 자료형이다: add_with_priority(), decrease_priority() 그리고 extract_min()이다. 이전에 언급했듯이, 이런 자료구조를 사용하면 기본 큐를 사용하는 것 보다 계산 시간이 더 빨라질 수 있다. 특히, 피보나치 힙 (Fredman & Tarjan 1984)이나 브로들 큐는 이 3가지 연산에 대해서 최적의 수행을 제공한다. 알고리즘이 약간 다르기 때문에 아래에 의사 코드로 나타냈다:
1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // 초기화
3
4      create vertex set Q
5
6      for each vertex v in Graph:
7          if v ≠ source
8              dist[v] ← INFINITY                          // 소스에서 v까지의 아직 모르는 길이
9          prev[v] ← UNDEFINED                             // v의 이전 노드
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                          // 메인 루프
15         u ← Q.extract_min()                         // 최고의 꼭짓점을 제거하고 반환한다
16         for each neighbor v of u:              // Q에 여전히 남아 있는 v에 대해서만
17             alt ← dist[u] + length(u, v)
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev
초기화 단계에서 우선순위 큐에 모든 꼭짓점을 채우는 대신에, 소스만을 포함하도록 초기화 할 수 있다. 그러면, if alt < dist[v] 블록에서 (decrease_priority 연산을 하는 대신에) 꼭짓점이 큐에 없다면 꼭짓점을 큐에 삽입해야 한다.
실제로 더 빠른 계산 시간을 얻기 위해서 다른 자료구조를 사용할 수 있다.

정확성의 증명

데이크스트라 알고리즘은 방문한 노드에 쓰여진 숫자를 이용하여 귀납적으로 증명할 수 있다.
시작점에서 노드로 갈 수 있는 경로가 있는 경우, 방문한 노드 v에 대해, 거리[v]는 시작점부터 v까지 가장 짧은 거리이고, 방문하지 않은 노드 u에 대해 거리[u]는 시작점부터 u까지 가장 짧을 것으로 추정되는 거리이다.
시작점에서 노드로 갈 수 없는 경우가 없다면 노드까지의 거리는 무한대로 둔다.
(참고: 방문하지 않은 정점 u에 대해 거리[u]는 실제 최단거리가 아니다.)
그래프에 시작점만 있는 경우, 위의 가설은 자명하며, 수학적 귀납법의 기저사례로 사용된다.
그렇지 않으면, 이 가정이 방문한 꼭짓점이 n-1일 때 성립한다고 가정하자. 이 경우에, 모든 미방문 꼭짓점에서 dist[u]가 가장 작은 u에 대해서 dist[u] = dist[v] + length[v,u]을 만족하는 변 vu를 선택한다. dist[u]는 source에서 u까지의 가장 짧은 거리로 볼 수 있다. 만약 그 경로보다 더 짧은 경로가 있고, 그 경로의 첫 번째 미방문 꼭짓점을 w라고 한다면 처음의 가정인 dist[w] > dist[u]에 의해서 모순이 생긴다. 이와 비슷하게, u로 가는 경로 중 미방문 꼭짓점을 지나지 않는 더 짧은 경로가 있고, 그 경로의 마지막 꼭짓점이 w라고 한다면, dist[u] = dist[w] + length[w,u]이여야 하기 때문에 여전히 모순이 생긴다.
u를 처리하고 나서도 각각의 미방문 꼭짓점 w에 대해서, dist[w]는 여전히 방문한 꼭짓점만을 통해서 source에서 w로까지의 최단 거리이다. 그 이유는 u를 통과하지 않는 경로 중 더 짧은 경로가 있다고 한다면 이미 찾았었을 것이며, u를 통하는 경로가 더 짧다면 u를 처리할 때 갱신되었을 것이기 때문이다.

세분화된 변형

변의 비용이 작은 정수일 때(C 보다 작을 때), 데이크스트라 알고리즘의 속도를 높이기 위해서 단조 우선순위 큐를 쓸 수 있다. 이 종류의 첫 번째 알고리즘은 Dial's algorithm으로, 버켓 큐를 사용해서 수행 시간이 로, 정수 가중치를 갖는 그래프의 가중 지름에 의존한다(Dial 1969). 판엠더 보아스 트리를 우선순위 큐로 사용하면 복잡성은 가 된다(Ahuja 외. 1990). 새로운 기수 힙과 잘 알려진 피보나치 힙의 결합에 기반한 수행은 의 시간이 소요된다(Ahuja 외. 1990). 마지막으로, 여기에서 언급한 특수한 경우에 대한 최적의 알고리즘은 다음과 같다. (Thorup 2000)의 알고리즘은 의 시간이 소요되고 (Raman 1997)의 알고리즘은 의 시간이 소요된다.
또한 유향 비순환 그래프에서는 꼭짓점의 위상적 순서를 처리하고 각각의 꼭짓점까지의 길이를 들어오는 변을 통한 경로 중 최소 거리로 설정하면 주어진 시작점에서 선형 시간 만에 최단 경로를 찾을 수 있다.
가중치가 정수인 무향 연결 그래프의 경우의 데이크스트라 알고리즘은 (Thorup 1999)에 의해 완전히 선형 복잡도 를 가진다.

관련 문제와 알고리즘

데이크스트라의 원 알고리즘의 기능성은 변형의 다양성을 통해 확장할 수 있다. 예를 들면, 종종 수학적으로 덜 최적인 해법을 나타내는 것이 바람직할 때가 있다. 최적 이하의 해법의 순위표를 얻기 위해서는 먼저 최적 해법을 계산해야 한다. 최적 해법의 한 변을 그래프에서 제거하고, 이 새로운 그래프에서 최적 해법을 계산한다. 원래 해법의 각각의 변을 차례로 제거하고 새로운 최단 경로를 계산한다. 그러면 두 번째 해법을 순위매기고 첫 번째 최적 해법의 다음에 표시한다.
데이크스트라 알고리즘은 종종 링크 상태 라우팅 프로토콜의 원리에 의해 작동하며, OSPF와 IS-IS가 그중 가장 일반적인 것이다.
데이크스트라 알고리즘과는 달리, 벨먼-포드 알고리즘은 소스 꼭짓점 s에서 도달할 수 있는 음수 사이클이 없으면 음수 가중치가 있을 때에도 사용할 수 있다. 이런 사이클이 존재하면, 이 사이클에 들어가서 한 바퀴를 돌 때 마다 전체 비용이 감소하기 때문에 최단 경로가 없다. 데이크스트라 알고리즘에 (음수 변을 제거하고 음수 사이클을 감지하기 위해)벨먼-포드 알고리즘을 결합해서 음수 가중치를 다룰 수 있으며, 이런 알고리즘은 존슨 알고리즘이라고 불린다.
A* 알고리즘은 데이크스트라 알고리즘을 일반화 한 것으로, 목적지까지의 "거리"의 하한에 관한 정보를 얻을 수 있을 때 탐색해야 할 부분 그래프의 크기를 줄일 수 있다. 이 접근은 선형 계획법의 관점에서 볼 수 있다: 최단 경로의 계산에서 선형 계획법이 있고, 그 쌍대 선형 계획법의 해법이 실행 가능하다는 것은 일관 휴리스틱을 형성한다는 것이다(대략적으로 말하면, 서명 관례가 문헌마다 다르기 때문이다). 이 실행 가능한 쌍대 / 일관 휴리스틱은 음이 아닌 감소 비용을 정의하고 A*은 본질저그로 이 감소 비용을 가지고 데이크스트라 알고리즘을 돌리는 것이다. 쌍대 선형 계획법이 약한 허용성 조건을 만족하면, A*는 벨먼-포드 알고리즘에 더 비슷하다.
데이크스트라 알고리즘의 기초가 되는 과정은 프림 알고리즘에서 사용되는 탐욕 과정과 유사하다. 프림 알고리즘의 목적은 그래프에 있는 모든 꼭짓점을 연결하는 최소 신장 트리를 찾는 것이나, 데이크스트라 알고리즘은 꼭짓점 두 개 만을 고려하는 것이다. 프림 알고리즘은 시작 꼭짓점의 전체 가중치로 평가하지 않고 각각의 가중치만을 평가한다.
너비 우선 탐색은 데이크스트라 알고리즘을 비가중 그래프에서, 우선순위 큐를 선입선출(FIFO) 큐로 만든 특수한 경우로 볼 수 있다.
빠른 행진 방법은 삼각형 메쉬의 지오데식 거리를 계산하는 데이크스트라 알고리즘의 연속적인 버전으로 볼 수 있다.

동적 계획법의 관점

동적 계획법의 관점에서 보면, 데이크스트라 알고리즘은 도달 방법에서 생겨난 최단 경로 문제에 대한 동적 계획법 함수적 방정식을 푸는 연속적 근사 계획법이다.
사실, 알고리즘의 바탕이 되는 논리에 대한 데이크스트라의 설명
문제 2. 주어진 두 개의 꼭짓점 와 사이의 최소 거리를 가지는 경로를 찾아라.
이 에서 로 가는 최단 경로에 있는 꼭짓점이라면, 이 경로는 마찬가지로 에서 까지 가는 최단 경로라는 사실을 이용한다.
은 벨먼의 유명한 최적성의 원리를 최단 경로 문제의 맥락에서 해석한 것이다.