Algorithms

Dijkstra's Algorithm

杉山空 2023. 9. 11. 21:23
728x90

본문의 내용은 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의 형태를 띤다)

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

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

 

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

AI에 연결된 vertices

B.  남은 노드들 즉, VA를 의미한다.

 

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

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

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

  이를 BII가 빈 집합이 될 때까지 반복한다. 그러면 우리가 원하는 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의 논문에서와는 달리 uV 에서 vV로의 shortest path의 weight를 du,v로 표현하겠다.

  Dijkstra가 이용한 아이디어는 Floyd의 paper에 적힌 것과 같다.[6] 이 아이디어는 두 vertices P, QV에 대하여, P에서 Q로의 shortest path에 포함되는 vertex RV에 대해 dP,Q=dP,R+dR,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이다. 

 

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

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

 

이 과정을 QA일 때 까지 반복한다.

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

 

Computational Complexity Analysis

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

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

728x90

'Algorithms' 카테고리의 다른 글

きたまさ法 / 키타마사법 / Kitamasa Method  (0) 2023.10.10
Knuth-Morris-Pratt Algorithm  (1) 2023.10.02
Segment Tree with Bitset  (0) 2023.08.09
이분 탐색  (0) 2023.05.08
The Segment Tree with the Maximum Sum  (0) 2023.04.06