본문의 내용은 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은
Dijkstra는 이 문제를 해결하기 위해 edges를 원소로 가지는 3가지 sets과 vertices를 원소로 가지는 2가지 sets을 이용했다.
먼저, edges를 원소로 가지는 3가지 sets이다.
그리고 vertices를 원소로 가지는 2가지 sets이다.
Dijkstra는 초기상태에서
이를
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의 논문에서와는 달리
Dijkstra가 이용한 아이디어는 Floyd의 paper에 적힌 것과 같다.[6] 이 아이디어는 두 vertices
Solution에서 Dijkstra는 sets을 정의하는데, 이번에는 3개의 vertex set과 3개의 edge set을 정의한다.
아래는 3가지 vertex sets이다.
아래는 3가지 edge sets이다.
초기 상태에서는 출발점
이 과정을
Step을 설명하는 부분에서 이 algorithm에 대한 어느 정도의 증명이 되었다고 생각할 수 있다. 앞서 설명한 아이디어를 활용할 수 있는데, 이 algorithm을 그대로 따라가거나, 역순으로 따라가는 형식으로 증명할 수 있다. - 귀납법과 유사한 방법을통해 -
Computational Complexity Analysis
이 챕터에서는 단순히 Dijkstra's algorithm으로 알려진 shortest path를 구하는 algorithm에 대해서만 다루겠다.
Dijkstra는 computational complexity에 대한 내용을 그의 paper에 담지 않았다. 하지만, 기존의 algorithm보다 뛰어나다고는 주장했다. 사실, 당시에는 좋은 성능의 queue가 존재하지 않았기 때문에 일일히 정의한 set에 포함된 모든 원소를 확인해야 했다. 그래서 처음 출판되었을 당시의 time complexity을 asympotic notation으로 표현하면
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
'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 |