Dijkstra's Algorithm is not Optimal SSSP Algorithm

개요

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths 논문 번역입니다.

작성 중인 글입니다. 이상한 부분이 있으면 알려주세요.

1. 서론

음수가 아닌 가중치 $w : E \rightarrow \mathbb R _{\ge 0}$를 갖는 $m$개의 간선과 $n$개의 정점을 갖는 그래프 $G = (V, E)$에 대해서, 단일 시작점 최단 경로(single-source shortest path, SSSP) 문제란 시작 정점 $s$에서 모든 정점 $v \in V$로의 최단 경로의 길이를 고려하는 문제이다.

교과서적인 다익스트라 알고리즘Dij59에 피보나치 힙FT87이나 Relaxed heap DGST88과 같은 고급 자료구조를 사용해서 $O(m + n \log n)$ 시간안에 SSSP를 해결할 수 있다. 이 방법은 비교-덧셈 모형(comparison-addition model)을 사용하며, 이 모형은 간선 가중치에 대해서 오로지 비교 연산과 덧셈 연산 만을 허용하며, 각 연산에 일정한 시간이 소모된다. 무향 그래프에 대해서, Pettie와 Ramachandran PR05은 비교-덧셈 모델에서 $O(m \alpha (m, n) + \min{n \log n, n \log\log r})$ 시간에 동작하는 계층-기반(hierarchy-based) 알고리즘을 제안했다. 여기서 $\alpha$는 역-아커만 함수(inverse-Ackermann function)이며, $r$은 두 간선 가중치 사이 비율에 대한 제한을 나타낸다.

다익스트라 알고리즘은 부수적으로 거리에 따른 정점의 순서를 계산하기도 한다. Haeupler, Hladík, Rozhoň, Tarjan, Tětek HHR+24의 최신 연구에 따르면, 시작점로부터 떨어진 거리에 따른 정점의 순서를 계산해야한다면 다익스트라 알고리즘이 최적임이 증명되었다. 그러나 만약 오로지 시작점로부터 떨어진 거리만 필요하며 정점의 순서는 필요하지 않은 경우, Duan, Mao, Shu, Yin DMSY23이 무향 그래프에 대해서 $O(m \sqrt{\log n \log \log n})$ 시간 무작위 알고리즘(Randomized algorithm)을 제공했다. 이는 희소 그래프(sparse graph)에서 $O(n \log n)$보다 더 나은 성능을 보인다. 그러나 방향 그래프(directed graph)에서는 아직 이러한 정렬 장벽(sorting barrier)을 깨지 못한 상태다.

1.1 논문의 목표

이 논문에서는 희소 그래프에서 정렬 병목을 해결한 실수 가중치의 유향 그래프에 대한 첫 SSSP 알고리즘을 소개하고자 한다.

Theorem 1.1. There exists a deterministic algorithm that takes $O(m \log ^{2/3} (n))$ time to solve the single-source shortest path problem on directed graphs with real non-negative edge weights.

정리 1.1. 간선이 음수가 아닌 실수 가중치를 갖는 유향 그래프에 대해서, $O(m \log ^{2/3} (n))$ 시간에 단일 시작점 최단 경로 문제를 해결하는 결정론적 알고리즘이 존재한다.

DMSY23에 등장하는 알고리즘은 무작위 알고리즘 방식이므로, 우리의 결과 또한 무향 그래프에서도 $O(m + n \log n)$ 시간 상한을 깨는 첫 결정론적 알고리즘이다.

Technical Overview. 단일 시작점 최단 경로 문제를 푸는 전통적인 알고리즘은 크게 두가지로 나눌 수 있다.

• 다익스트라 알고리즘(Dijkstra’s algorithm) Dij59: 우선순위 큐를 이용해서, 매번 시작점로부터 가장 가까운 거리에 있는 정점 $u$를 추출하고, 정점 $u$로부터 나가는 모든 간선을 이완(relax)한다. 이 과정은 대개 시작점로부터 거리에 대해 정렬하기 때문에, 최소 $\Theta(n\log n)$의 시간복잡도를 갖는다.
• 벨만-포드 알고리즘(Bellman-Ford algorithm) Bel58: 동적 프로그래밍(dynamic programming)에 기반하여 여러 번 이완(relax)를 수행한다. 최대 $k$개의 간선으로 이루어진 최단 경로를 찾기 위해서 벨만 포드 알고리즘은 정렬 없이 $O(mk)$ 시간 안에 최단 경로를 계산할 수 있다.

Edge relaxation: 가중치 있는 그래프에서 각 edge에 배정되어 있는 만큼의 가중치를 더해가며 탐색할 때, 더 나은 경로의 가중치가 있다면 그 값으로 업데이트하는 것을 의미합니다. 더 나은 대안으로 업데이트한다는 뜻이며, 이 작업을 이완(relax)라고 부릅니다. Note

우리의 접근법은 [GT88, CKT+16, DLWX18]의 병목 경로 알고리즘(bottleneck path algorithm)에서 사용된 방법과 비슷하게, 재귀적 분할 기법(recursive partitioning technique)을 통해서 두 방법을 결합한다.

다익스트라 알고리즘을 실행 중에는, 우선순위 큐(힙)는 ‘완료되지 않은(incomplete)’ 정점 $u$의 집합인 ‘경계 집합(Frontier)’ $S$를 관리한다. 여기서 ‘완료되지 않은’ 정점이란 현재 추정 최단 거리 $\hat d[u]$가 실제 최단 거리 $d(u)$보다 큰 정점이다. 최단 경로 $s-u$는 어떤 완료된(complete) 정점 $v \in S$을 거쳐야 한다. 이 경우에, 우리는 정점 $u$가 정점 $v$에 ‘의존한다’라고 한다. (그러나, $S$에 속한 정점은 전부 완료되었다고 보장되지 않는다.) 다익스트라 알고리즘은 집합 $S$에서 시작점로부터 그저 가장 가까운 정점을 선택하고, 그 정점은 반드시 완료된 상태이며, 그 정점에 연결된 모든 간선은 이완된다.

알고리즘의 실행 시간 병목은 경계 집합에 $\Theta(n)$개의 정점이 포함 될 수 있기 때문에 발생한다. 우리는 항상 시작점로부터 가장 가까운 정점을 선택해야 하기 때문에, 정점간의 전체 순서를 관리해야 하며, 이 때문에 $\Omega(n \log n)$ 정렬 장벽을 넘을 수 없다. 우리의 핵심 아이디어는 이 경계 집합의 크기를 줄이는 것이다. 이제 상한값 $B$보다 작은 거리만을 고려하여 연산을 수행한다고 가정하자. 상한 $B$보다 작은 최단 거리 $d(u) < B$를 갖고, 최단 경로 $s-u$가 집합 $S$에 속한 정점을 지나는 정점 $u$의 집합을 $\tilde U$라고 하자. 이때 경계 집합의 크기를 $|\tilde U| /\log ^{\Omega (1)} (n)$ 또는 $1/\log^{\Omega (1)} (n)$개의 중요한 정점(vertices of interest)만 남기도록 제한할 수 있다. 매개변수로 $k = \log ^{\Omega (1)}(n)$를 설정하면, 두 가지 경우가 가능하다.

• 이미 $|\tilde U| > k |S|$인 경우, 경계 집합의 크기는 이미 $|\tilde U| / k$이다.
• 그렇지 않은 경우, $|\tilde U| \le k |S|$이다. 집합 $S$의 정점으로부터 벨만 포드 알고리즘을 $k$ 단계를 수행하면, $\tilde U$에서 $k$개보다 적은 정점으로 이루어진 최단 경로 $s-u$를 갖는 $\tilde U$에 속한 모든 정점 $u$이 완료된다. 그렇지 않다면, $S$에 속하는 어떤 정점 $v \in S$가 $u$에 의존하며, $v$에서 시작하는 최단 경로 트리는 $\tilde U$ 에 있는 정점이 $k$개 이상이어야 한다. 따라서 경계 집합 $S$를 “피벗(pivot)”의 집합으로 축소할 수 있고, 각 피벗마다 최단 경로 트리의 크기가 $k$ 이상이므로, 결론적으로 피벗의 개수는 $|\tilde U| / k$개로 제한된다.

알고리즘은 위 아이디어를 기반으로 한다. 경계 집합이 동적으로 변화하는 다익스트라 알고리즘 대신, $\log n/t$ 단계로 이루어진 분할정복 절차를 사용하며, 각 단계는 경계집합과 상한 $B$를 포함한다. 만약 나이브(naive)하게 구현한다면 각 경계 정점마다 $\Theta(t)$ 시간, 각 정점마다 $\Theta(\log n)$ 실행시간이 소모된다. 하지만 앞서 설명했듯이 경계 축소(frontier reduction)을 각 단계마다 적용한다면, $\Theta(t)$ 작업은 오로지 피벗에만 적용되고, 피벗은 오로지 $1 / \log ^{\Omega(1)}(n)$만큼만 존재하게 된다. 따라서 정점당 실행 시간은 $\log n / \log ^{\Omega(1)}(n)$으로 줄어들어, 상당한 속도 향상이 이루어지게 된다.

1.2 관련 연구

SSSP 문제의 경우, 알고리즘이 정수 가중치 간선에 대해 word RAM 모델에서 실행되는 것을 허용하면, $O(n\log n)$보다 더 나은 개선된 결과들이 등장했으며, [FW93, FW94, Tho00a, Ram96, Ram97, Tho00b, Hag00], 무향 그래프에 대한 Thorup의 선형 시간 알고리즘 Tho99 및 유향 그래프에 대해 $O(m + n \log \log \min \{n, C\} )$ 시간 알고리즘 Tho04을 통해 최고조에 도달했다. 여기서 $C$는 최대 가중치를 의미한다. 가중치가 음수인 그래프에 대해서는, 최근 획기적인 결과들이 했다. 음수 정수 가중치에 대한 준 선형 시간인 $O(m^{1+o(1)} \log C)$ 알고리즘 [CKL+22, BNWN22, BCF23], 음수 실수 가중치에 대해 강한 준세제곱 시간 (strongly subcubic time) 알고리즘 [Fin24, HJQ24] 등이 있다.

비교 기반 정렬 알고리즘에 대한 $\Omega(n \log n)$을 바탕으로, SSSP와 여러 유사한 문제들에 대해서 정렬 장벽(sorting barrier)이 존재한다고 믿어져 왔다. 그러나 많은 그래프 문제에서 정렬 장벽을 극복한 연구들이 나타났다. 예를 들어, Yao는 $O(m \log \log n)$ 시간에 최소 신장 트리(minimum spanning tree, MST)를 찾는 알고리즘을 제안했으며Yao75, 무작위화를 이용해 선형 시간으로 개선되었다. (randomized linear time) [KKT95]. Gabow와 Tarjan은 $s-t$ 병목 경로 문제를 $O(m \log ^* n)$ 시간에 해결했으며 [GT88], 이후 무작위화 기법을 통해 $O(m \beta (m, n))$까지 개선했다. 이때 $\beta(m, n) = \min \{ k \ge 1 : \log ^{(k)} n \le \frac m n \}$이다. 단일 시작점 모든 시작점 병목 경로로 문제 (single-source all-destination bottlenect path problem)의 경우, Duan, Lyu, Wu, Xie DLWX18는 무작위화 $O(m \sqrt{\log n})$ 시간 알고리즘을 제안했다. 단일 시작점 비감소 경로 문제(single-source nondecreasing path problem)의 경우, Virginia V. Williams Wil10는 $O(m \log \log n)$ 시간 알고리즘을 제안했다.

2. Preliminaries

우리는 음수가 아닌 실수 가중치 함수 $w : E \rightarrow \mathbb R_{\ge 0}$를 갖는 유향 그래프 $G = (V, E)$를 고려하며, 두 정점 $u, v$를 잇는 간선의 가중치를 $w_{uv}$로 나타낸다 ($(u, v) \in E$). 정점의 개수를 $n = |V|$, 간선의 개수를 $m = |E|$로 나타낸다. SSSP 문제에서, 우리는 시작 정점을 $s$라고 가정한다. 알고리즘의 목표는 시작점 $s$에서 모든 정점 $v \in V$로의 최단 경로의 길이 $d(v)$를 계산하는 것이다. 일반성을 잃지 않고, 그래프 $G$의 모든 정점은 $s$로부터 도달할 수 있다고 가정하며, 따라서 $m \ge n - 1$ 이다.

Constant-Degree Graph. 이 논문에서 우리는 그래프가 상수 차수(constant-degree, 정점의 in-degree 및 out-degree)에서 동작한다고 가정한다. 어떤 그래프 $G$에 대해서도 고전적인 다음 방식의 ([Fre83]과 비슷한) 변환을 통해 그래프 $G’$를 만들 수 있다.

• 각 정점 $v$를 0의 가중치 간선으로 강하게 연결된 (strongly connected) 정점의 사이클로 대체한다. 기존 $v$와 연결된 다른 정점 $w$ 마다, 정점 $x_{vw}$를 사이클에 추가한다.
• 그래프 $G$의 모든 간선 $(u, v)$에 대해, 정점 $x_{uv}$로부터 $x_{vu}$로 가는 간선을 추가한다. 이때 가중치는 $w_{uv}$이다.

위 변환은 명백히 기존 그래프의 최단경로를 보존하며, 그래프 $G’$의 모든 정점의 in-degree와 out-degree는 최대 2 이므로, $G’$는 $O(m)$개의 정점과 $O(m)$개의 간선을 갖는 그래프가 된다.

Comparison-Addition Model. 우리의 알고리즘은 비교-덧셈 모델에서 동작한다. 이 모델은 모든 간선 가중치에 대해서 오로지 비교 및 덧셈 연산만 허용하며, 각 연산은 일정한 시간(unit time)이 소요된다. 가중치에 대해서 이외의의 어떤 계산도 허용되지 않는다.

Labels Used in the Algorithm. 정점 $v \in V$에 대해, $d(u)$는 시작점 $s$에서 정점 $u$로 가는 최단 경로의 길이를 의미한다. 다익스트라 알고리즘과 유사하게, 본 알고리즘은 $d(u)$의 추정치로서 전역 변수 $\hat d[u]$를 유지하며, 항상 $\hat d[u] \ge d(u)$를 만족한다. 처음에는 $\hat d[s] = 0$이며, 나머지 $v \neq s$인 모든 $v$에 대해 $\hat d[v] = \infty$로 설정한다. 알고리즘은 간선 $(u, v) \in E$에 대해, $\hat d[u]$를 감소하지 않는 방식으로만 이완한다. 즉, $\hat d[v] + w_{uv} \le \hat d[u]$ 일 때만 $\hat d[u] \leftarrow \hat d[v] + w_{uv}$로 업데이트한다. 따라서 $\hat d[u]$가 가질 수 있는 값은 모두 $s$에서 $v$로 가는 어떤 경로의 길이에 해당한다. 만약 $\hat d[x] = d(x)$이면, 정점 $x$가 완료(complete) 되었다고 하며 그렇지 않다면 정점 $x$는 완료되지 않은(incomplete) 상태라고 한다. 어떤 정점 집합 $s$에 속한 모든 정점이 완료되었다면 집합 $S$가 완료(complete) 되었다고 한다. 완전성(completeness) 여부는 알고리즘의 진행 상황에 따라 달라질 수 있다. 또한 알고리즘은 현재의 $\hat d[\cdot]$ 값에 기반한 최단 경로 트리도 유지한다. 이를 위해 각 정접의 이전 정점(predecessor) Pred$[V]$에 기록한다. 간선 $(u, v)$를 이완할 때 Pred$[u]$ $\leftarrow v$로 설정한다.

MathJax에는 \textsc 명령이 없습니다. 원 논문에서는 Pred[v]를 \textsc{Pred}[v]로 표기했지만, 여기서는 Pred[v]로 표기합니다.

Total order of Paths.

Assumption 2.1

When we relax an edge $(u, v)$:

When we compare two different $\hat d [u]$ and $\hat d [v]$ for $u \neq v$:

3. The Main Result

3.1 The Algorithm

3.2 Observations and Discussions on the Algorithm

3.3 Correctness Analysis

3.4 Time Complexity Analysis

Reference

[BCF23] Karl Bringmann, Alejandro Cassis, and Nick Fischer. Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster! . In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 515–538, Los Alamitos, CA, USA, November 2023. IEEE Computer Society

[Bel58[]] Richard Bellman. On a routing problem. Quarterly of Applied Mathematics, 16:87–90, 1958.

[BFP+73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448–461, 1973.

[BNWN22] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight singlesource shortest paths in near-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 600–611, 2022.

[CKL+22] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.

[CKT+16] Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck paths and trees and deterministic graphical games. In Nicolas Ollinger and Heribert Vollmer, editors, STACS, volume 47 of LIPIcs, pages 27:1–27:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

[DGST88] James R. Driscoll, Harold N. Gabow, Ruth Shrairman, and Robert E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Commun. ACM, 31(11):1343–1354, November 1988.

[Dij59] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.

[DLWX18] Ran Duan, Kaifeng Lyu, Hongxun Wu, and Yuanhang Xie. Single-source bottleneck path algorithm faster than sorting for sparse graphs. CoRR, abs/1808.10658, 2018.

[DMSY23]: R. Duan, J. Mao, X. Shu, and L. Yin. A randomized algorithm for single-source shortest path on undirected real-weighted graphs. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 484–492, Los Alamitos, CA, USA, November 2023. IEEE Computer Society.

[Fin24] Jeremy T. Fineman. Single-source shortest paths with negative real weights in $\tilde O (mn^{8/9})$ time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 3–14, New York, NY, USA, 2024. Association for Computing Machinery.

[Fre83] Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 252–257, New York, NY, USA, 1983. Association for Computing Machinery.

[FT87] M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. JACM, 34(3):596–615, 1987.

[FW93] Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424–436, 1993.

[FW94] Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. Journal of Computer and System Sciences, 48(3):533–551, 1994.

[GS78] Leo J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages 8–21, 1978.

[GT88] Harold N Gabow and Robert E Tarjan. Algorithms for two bottleneck optimization problems. Journal of Algorithms, 9(3):411–417, 1988.

[Hag00] Torben Hagerup. Improved shortest paths on the word RAM. In Ugo Montanari, José D. P. Rolim, and Emo Welzl, editors, Automata, Languages and Programming, pages 61–72, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.

[HHR+24] Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan, and Jakub Tětek. Universal optimality of dijkstra via beyond-worst-case heaps. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024.

[HJQ24] Yufan Huang, Peter Jin, and Kent Quanrud. Faster single-source shortest paths with negative real weights via proper hop distance, 2024.

[KKT95] David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42(2):321–328, March 1995.

[PR05] Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing, 34(6):1398–1431, 2005.

[Ram96] Rajeev Raman. Priority queues: Small, monotone and trans-dichotomous. In Proceedings of the Fourth Annual European Symposium on Algorithms, ESA ’96, page 121–137, Berlin, Heidelberg, 1996. Springer-Verlag.

[Ram97] Rajeev Raman. Recent results on the single-source shortest paths problem. SIGACT News, 28(2):81–87, June 1997.

[Tho99] Mikkel Thorup. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM, 46(3):362–394, May 1999.

[Tho00a] Mikkel Thorup. Floats, integers, and single source shortest paths. J. Algorithms, 35(2):189–201, May 2000.

[Tho00b] Mikkel Thorup. On RAM priority queues. SIAM Journal on Computing, 30(1):86–109, 2000.

[Tho04] Mikkel Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. Journal of Computer and System Sciences, 69(3):330–353, 2004. Special Issue on STOC 2003.

[Wil64] J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347–348, 1964.

[Wil10] Virginia Vassilevska Williams. Nondecreasing paths in a weighted graph or: How to optimally read a train schedule. ACM Trans. Algorithms, 6(4), September 2010.

[Yao75] Andrew Chi-Chih Yao. An $O(|E|\log\log|V|)$ $algorithm for finding minimum spanning trees. Information Processing Letters, 4(1):21–23, 1975.