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)$를 설정하면, 두 가지 경우가 가능합니다.

• TODO

• TODO

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.