Dijkstra's Algorithm

본문의 내용은 E. W. Dijkstra의 A Note on Two Problems in Connexion with Graphs[1]에 관한 간단한 리뷰이다.

 

Introduction

  Dijkstra's algorithm은 non-negative weighted graph에서 shortest path를 찾는 well-known algorithm이다. 현재 우리에게는 교과서[2]나, 알고리즘 문제해결과 관련된 서적에 적힌 버전이 널리 알려져 있다. 이번 글에서는 Dijkstra's algorithm의 초기 버전과 주로 Prim's algorithm[3]이라 불리는 minimum spanning tree(MST)를 찾는 알고리즘에 대해서 다루고자 한다.

 

Minimum Spanning Tree[1]

  MST를 찾는 알고리즘 중 가장 잘 알려진 것이 Kruskal's algorithm[4]과 Prim's algorithm이다. 이중 Prim's algorithm의 경우 Dijkstra의 논문 A Note on Two Problems in Connexion with Graphs에서도 소개된다. - E. W. Dijkstra가 따로 발견했다. - 이 둘보다 먼저 Jarnik[5]이 이 알고리즘을 발견하긴 했지만, 대한민국에서 잘 알려져 있지는 않다.

 

  우리는 non-negative 가중치를 가지는 weighted graph를 고려해야 한다. 이 그래프의 vertex set은 \(V\), edge set은 \(E\)라 하겠다. 이제 이 graph에서 MST를 찾아야 한다. 이제 Dijkstra의 발견에 대해 알아본다.

 

Dijkstra는 이 문제를 해결하기 위해 edges를 원소로 가지는 3가지 sets과 vertices를 원소로 가지는 2가지 sets을 이용했다.

먼저, edges를 원소로 가지는 3가지 sets이다.

\(I\).  구축중인 tree에 포함된 edge들. (우리가 구하고자 하는 해의 subtree의 형태를 띤다)

\(II\).  \(I\)에 포함된 edge들로 부터 선택될 수 있는 edges. 즉, 현재 방문한 vertices와 연결된 edges 중 아직 사용하지 않은 edges

\(III\).  남은 edges. (아직 고려되지 않음)

 

그리고 vertices를 원소로 가지는 2가지 sets이다.

\(A\).  \(I\)에 연결된 vertices

\(B\).  남은 노드들 즉, \(V-A\)를 의미한다.

 

  Dijkstra는 초기상태에서 \(A\)에 vertex 하나를 포함시켰다. 이 vertex는 임의로 정해주어도 좋다. 이 상태에서 \(I=\phi\) 이고,  \(III \cup II=E\)이다. Dijkstra는 2 개의 step을 통해 MST를 찾는 방법을 제안했다.

\(Step \; 1\). \(II\)에서 shortest edge를 골라 \(II\)에서 제거한다. 그리고 이 edge를 \(I\)에 추가한다. 이때, 방문하게 되는 vertex도 \(B\)에서 제거하고, \(A\)에 추가한다. Shortest edge란 weight가 가장 작은 edge를 의미한다.

\(Step \; 2\). \(Step \; 1\)에서 제거한 vertex에 연결된 edges를 확인하고 \(II\)에 추가한다. 이때 \(II\)에 이미 존재하는 edge와 같은 vertex such that \(\in B\)와 연결된다면, \(II\)에 존재하는 edge와 weight를 비교해야 한다. 만약 추가하려고 하는 edge의 weight가 이미 \(II\)에 들어있던 edge의 weight보다 작다면 \(II\)에 들어있던 edge를 제거하고 추가하려고 하는 edge를 \(II\)에 추가한다. 아니면, 이 작업을 무시한다. 조금 더 자세하게 서술하면, 지금 확인하고 있는 edge를 \(e\ \mathrm{such} \ \mathrm{that} \ \mathrm{connected} \ \mathrm{with}\ v \in B\) 라 하자. 그리고 \(II\)에 존재하는 edge는 \(e'\ \mathrm{such} \ \mathrm{that} \ \mathrm{connected} \ \mathrm{with}\ v \in B\) 이다. \(e\)와 \(e'\)중 weight가 작은 것을 골라 \(II\)에 포함시키고 나머지 하나는 삭제한다고 생각하면 된다. - \(e\)의 weight가 더 크다면 추가하지 않는다. - 

  이를 \(B\)와 \(II\)가 빈 집합이 될 때까지 반복한다. 그러면 우리가 원하는 MST에 포함되는 edges가 포함된 \(I\)를 얻을 수 있다. 

 

Dijkstra는 이 방법이 Kruskal의 방법에 비해 dense한 graph에서 효율적이라 주장했다.

 

  p.s) 이 방법이 올바르게 작동하는 것에 대해 의문을 가질 수 있다. Kruskal의 paper에서는 그의 algorithm에 관한 증명을 확인할 수 있지만[4] Dijkstra의 논문에는 그런 것이 없다. 하지만, 간단하게 생각해 보면, Kruskal's algorithm이 위 algorithm과 크게 다르지 않다. 현재 선택할 수 있는 edges 중에서 가장 weight가 작은 edge를 선택해야 한다. 이는 Krusukal's algorithm에서 전체 edges 중 weight가 작은 edge부터 선택하는 것과 같은 결과를 낳는다. - 단, MST가 유일하다면 -

*같은 알고리즘을 다루는 Prim의 paper에서는 증명에 관해 약간 설명이 되어 있다.[3]

 

Shortest Path[1]

  Dijkstra가 본문에서 다룬 2번째 문제는 두 vertices 간의 shortest path이다. 설명의 편의를 위해 이 글에서는 Dijkstra의 논문에서와는 달리 \(u \in V\) 에서 \(v \in V\)로의 shortest path의 weight를 \(d_{u,v}\)로 표현하겠다.

  Dijkstra가 이용한 아이디어는 Floyd의 paper에 적힌 것과 같다.[6] 이 아이디어는 두 vertices \(P,\ Q \in V\)에 대하여, \(P\)에서 \(Q\)로의 shortest path에 포함되는 vertex \(R \in V\)에 대해 \(d_{P,Q}=d_{P,R}+d_{R,Q}\)가 성립한다는 잘 알려진 사실이다.

  Solution에서 Dijkstra는 sets을 정의하는데, 이번에는 3개의 vertex set과 3개의 edge set을 정의한다.

아래는 3가지 vertex sets이다.

\(A\). \(P\)로 부터의 shortest path가 알려진 vertices와 그 shortest path의 weight pairs.

\(B\). 아직 \(A\)에 포함되지 않은 vertices 중, \(A\)에 포함된 vertices와 인접한 vertices

\(C\). 나머지 vertices

 

아래는 3가지 edge sets이다.

\(I\). \(P\)로 부터 \(A\)에 포함된 vertices까지의 shortest paths ; 이 paths는 edges로 표현된다.

\(II\). \(I\)에 포함된 path의 끝부분에 추가했을때, \(B\)에 포함된 vertex로 이어지는 edges ; \(E\)에 포함된 edges 중에서 \(B\)에 포함된 vertex와 \(A\)에 포함된 vertex를 연결하는 edges

\(III\). 나머지 edges ; 무시되었거나, 아직 확인하지 않은 것들

 

  초기 상태에서는 출발점 \(P\)만이 \(A\)에 포함되어 있다. 나머지 모든 vertices는 \(C\)에 포함되어 있고, 모든 edges는 \(III\)에 포함되어 있다. 이제 아래의 2개의 steps를 통해 문제를 해결할 수 있다. 도착점은 \(Q\)이다. 

 

\(Step \; 1\). \(A\)의 vertex에서 \(B\)나 \(C\)에 포함된 vertex \(R\)을 향하는 모든 edges를 확인한다. 만약 \(R \in B\)라면, \(P\)에서 \(R\)까지의 shortest path의 weight를 \(II\)를 이용한 결과와 현재 확인하는 edge를 이용하는 path의 weight와 비교한다. \(II\)의 edge를 이용한 path의 weight가 다른 곳에 있던 edge를 이용한 path의 weight가 더 작으면, \(II\)에 있던 edge를 현재 확인하고 있는 edge로 대체한다. 만약 \(R \in C\)라면 \(R\)을 \(B\)로 옮기고, \(II\)에 현재 확인하고 있는 edge를 추가한다.

\(Step \; 2\). \(Step \; 1\)이 끝난 후에 \(B\)를 확인한다고 하자. \(II\)의 edge를 이용하면 \(B\)에 포함된 vertices는 \(P\)와 연결될 수 있고, distance를 가진다. - weight of shortest path - ; \(I\)에 \(II\)의 edge를 연결하여 \(P\)로 부터 \(B\)에 포함된 vertices까지의 shortest path를 구할 수 있다. 이제 \(B\)에 포함된 vertices와 \(P\)로 부터 \(B\)에 포함된 vertices까지의 shortest path의 distance를 \(A\)에 삽입하고 \(B\)에서 이 vertices를 제거한다. 또, shortest path를 \(I\)에 삽입한다.

 

이 과정을 \(Q \in A\)일 때 까지 반복한다.

Step을 설명하는 부분에서 이 algorithm에 대한 어느 정도의 증명이 되었다고 생각할 수 있다. 앞서 설명한 아이디어를 활용할 수 있는데, 이 algorithm을 그대로 따라가거나, 역순으로 따라가는 형식으로 증명할 수 있다. - 귀납법과 유사한 방법을통해 - 

 

Computational Complexity Analysis

 이 챕터에서는 단순히 Dijkstra's algorithm으로 알려진 shortest path를 구하는 algorithm에 대해서만 다루겠다.

  Dijkstra는 computational complexity에 대한 내용을 그의 paper에 담지 않았다. 하지만, 기존의 algorithm보다 뛰어나다고는 주장했다. 사실, 당시에는 좋은 성능의 queue가 존재하지 않았기 때문에 일일히 정의한 set에 포함된 모든 원소를 확인해야 했다. 그래서 처음 출판되었을 당시의 time complexity을 asympotic notation으로 표현하면 \(\Theta(|V|^2)\)이 된다. 모든 \(Step \; 1\)과 \(Step \; 2\)를 수행하는데 \(Theta(|V|)\)만큼이 소요되고, 이를 모든 vertices에 대해 수행해야 하기 때문에 이런 결과가 얻어진다. 더 정확하게, set의 원소를 관리하는 것을 빠르게 할 수록 time complexity는 줄어든다. 만약, set에서 \(N\)개의 원소를 관리하는데 \(O(\log |N|)\) 만큼의 연산이 필요하다면, Dijkstra's algorithm의 time complexity는 \(\Theta(|E|+|V| \log |V|)\) 까지도 줄어들 수 있다.[7]

 

 

Reference

[1] Edsger W D (1959) Numerische Mathematic 1: 269-271

[2] Thomas H C et al (2009) Introduction to Algorithms, Third Edition. The MIT Press. 

[3] Prim R C (1957) Shortest Connection Netwroks And Some Generalizations. Bell System Technical Journal 36(6):1389-1401

[4] Joseph B K (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7:48-50

[5] Jarník, Vojtěch (1930) O jistém problému minimálním. Práce moravské přírodovědecké společnosti 6, fasc. 4: pp. 57--63

[6] Robert W F (1962) Algorithm 97: Shortest Path. Commun. ACM 5(6):345. doi:10.1145/367766.368168

[7] Michael L F, Robert E T (1987) Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. J. ACM 34(3):596–615