CS Paper Radar

A Faster Undirected Single-Source Shortest Path Algorithm

Avi Kadria, Liam Roditty

cs.DS ·submitted 2026-09-14 09:05 UTC · v1

Abstract

The single-source shortest paths (SSSP) problem in graphs with non-negative edge weights is one of the most classic problems in algorithms. For decades, the best known running time in the comparison-addition model was the $O(m+n\log n)$ bound of Dijkstra's algorithm with Fibonacci heaps. Recently, Duan, Mao, Shu, and Yin (FOCS'23) gave a randomized $O(m\log^{1/2} n \log\log^{1/2} n)$-time algorithm for SSSP in weighted undirected graphs. For weighted directed graphs, Duan, Mao, Mao, Shu, and Yin (STOC'25) gave an $O(m\log^{2/3} n)$-time algorithm for SSSP. Very recently, Duan, Mao, Shu, and Yin (ICALP'26) obtained an algorithm for directed graphs whose running time matches the $O(m\log^{1/2} n \log\log^{1/2} n)$ time of the undirected case. In this paper, we present a faster algorithm for SSSP in weighted undirected graphs, giving the first improvement in running time since the FOCS'23 breakthrough of Duan, Mao, Shu, and Yin. Our algorithm runs in $O(m\log^{1/2} n \log\log^{1/4} n \log\log\log^{1/4} n)$ time, improving the previous running time by a factor of $(\frac{\log\log n}{\log\log\log n})^{1/4}$. Our main contribution is a simple and efficient tool that computes, for every vertex, its distance to the nearest vertex in a random sample; this tool may be of independent interest.

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Bounds for Directed SSSP in Sparse and Intermediate-Density Graphs

cs.DS ·2026-11-19 ·Valery, Grishin, Aryeh Lev Zabokritskiy
similarity 0.78
Abstract · 69 pages

We give a deterministic algorithm for exact single-source shortest paths (SSSP) in directed graphs with $n$ vertices, $m$ edges and nonnegative real edge weights. In the comparison-addition model, with unit-cost elementary operations on $O(\log(n+m+2))$-bit integer words, its running time for $m=O(n)$ is $O(n\sqrt{\log n}(\log\log n)^{1/4})$. For $m=Θ(n)$, this reduces the exponent of $\log\log n$ in the bound of Duan, Mao, Shu and Yin from $1/2$ to $1/4$ and removes the factor $(\log\log\log n)^{1/4}$ from the sparse bound stated in a public draft. The same algorithm improves on the bound of Duan et al. over a range of intermediate densities. At $m=Θ(n\sqrt{\log\log n})$, the running time is $O(n\sqrt{\log n}(\log\log n)^{5/8})$, reducing their exponent from $3/4$ to $5/8$. This is a consequence of a uniform bound for intermediate densities up to any fixed multiple of $n\log\log n$ edges; its validity range is larger than the range of strict improvement.

0.14

First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs

cs.DS ·2026-11-03 ·Eden Koveshi, Liam Roditty, Ariel Sapir
similarity 0.67
Abstract

We present the first four All-Pairs Approximate Shortest Paths (APASP) algorithms for decremental weighted undirected graphs. We extend the hierarchy induced edge sets of Baswana and Kavitha [FOCS'06 and SICOMP'10] to the decremental setting. At any point in time, for any $u,v$, $W_{i}$ denotes the weight of the $i$-th heaviest edge on any shortest path between them in the current graph. For any $\varepsilon>0$, our first algorithm maintains $(1+\varepsilon,2W_{2})$-APASP in $\tilde{O}(n^{\frac{3}{2}+o(1)}m^{\frac{1}{2}})$ total update time, matching a single static computation of Cohen and Zwick [SODA'97 and JALG'01], up to a subpolynomial factor. It also improves the stretch of the $(2+\varepsilon)$-APASP algorithm of Dory, Forster, Nazari and de Vos [ICALP'24]. Our second algorithm maintains $(1+\varepsilon,2W_{1}+2W_{2})$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time, improving upon Chechik's $(3+\varepsilon)$-APASP algorithm [FOCS'18] for $m=Ω(n^{\frac{11}{6}})$. We also obtain two $(1+\varepsilon,2\cdot(k-1)W_{1})$-APASP algorithms with total update times $\tilde{O}(n^{2-\frac{1}{k}+o(1)}m^{\frac{1}{k}})$ and $\tilde{O}(n^{2+\frac{2}{3k-2}+o(1)})$, adapting the static $+2\sum_{i=1}^{k-1}W_{i}$-APASP algorithms of Cohen and Zwick [SODA'97 and JALG'01] and Roditty and Sapir [FSTTCS'25]. For unweighted graphs, we present $(1+\varepsilon,2)$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time and $(1+\varepsilon,2\cdot(k-1))$-APASP in $\tilde{O}(n^{2+\frac{1}{3k-4}+o(1)})$. Combined with the results of Dory, Forster, Nazari and de Vos [ICALP'24], these match the fastest combinatorial static bounds of Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] up to subpolynomial factors.

0.27

Improved Massively Parallel Shortest Path Computation

cs.DC cs.DS ·2026-10-12 ·Yi-Jun Chang, Shaun Quek
hot direction similarity 0.67
Abstract

We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \in V$, the oracle returns $a$-approximate distances $δ(u,v)$ for all $v \in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\tildeΘ(n)$ memory, and the heterogeneous regime, where all machines have $Θ(n^γ)$ memory for some constant $γ\in (0,1]$, except for a single machine with $\tildeΘ(n)$ memory. We develop randomised algorithms that construct $O(1)$-approximate SSSP oracles in $O(\log\log n)$ rounds in the near-linear regime and in $O(\log^2\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, requires $\left(\log\log n\right)^{2+O(1/γ)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\tilde N_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $δ$ such that $\tilde N_k(u)$ consists of the $k$ vertices closest to $u$ according to $δ$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(γ)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\log^2\log n)$ rounds.

0.31

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

cs.DS ·2026-10-13 ·Vikrant Ashvinkumar
similarity 0.67
Abstract · More detailed AI statement. Polished exposition and fixed typos

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.

0.20

Faster Deterministic All-Pairs Shortest Paths with Real Edge Weights

cs.DS ·2026-11-12 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
similarity 0.65
Abstract · 33 pages. Revised proofs and presentation; streamlined the real-weight result

We give a deterministic algorithm for all-pairs shortest paths in directed $n$-vertex graphs with arbitrary finite real edge weights and no negative cycles. It computes all distances in $O(n^{2.9929729})$ worst-case time, improving both the recent deterministic bound $O(n^{2.9997})$ and the Las Vegas expected-time bound $O(n^{2.993805})$. We use a model with exact real addition, subtraction and comparison at unit cost; auxiliary integer arithmetic and indexed memory access are charged at bit cost.

0.12

A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth

cs.DS cs.CC ·2026-09-24 ·DongYun Byun, Akira Matsubayashi
theory similarity 0.65
Abstract · 22 pages, 1 figure. Presented in IPEC 2026

The $k$ vertex-disjoint paths problem asks whether, given a graph $G$ and $k$ pairs of vertices $(s_1,t_1)$, \ldots, $(s_k,t_k)$, $G$ has $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all $1\leq i\leq k$. If $G$ is undirected, then this problem is NP-complete, but there exist FPT algorithms parameterized by $k$.Since these algorithms involve an extremely large function on $k$, algorithms for restricted graphs have also been investigated. In particular, a $2^{2tw\log tw+O(tw)}\cdot n$ time algorithm for undirected graphs with $n$ vertices and treewidth $tw$ is proposed by Scheffler (Technical Report 396, TU Berlin, '94), and it is proved by Lokshtanov, Marx, and Saurabh (SIAM J. Comput. '18) that, under the ETH, there exists no $2^{o(pw\log pw)}\cdot n^{O(1)}$ time algorithm for either directed or undirected graphs with pathwidth $pw$ and for $k=Ω(pw^4)$. It has not been known whether the lower bound also holds for a smaller $k$. In this paper, we prove that, for both the directed and undirected cases, there is an algorithm faster than Lokshtanov et al.'s lower bound for $k=tw^{o(1)}$ by proposing a $2^{O((tw+k)\log k)}\cdot n$ time algorithm. Besides, we prove a lower bound that, under the SETH, there exists no $(2-ε)^{pw\log pw}\cdot n^{O(1)}$ time algorithm for directed graphs and for a general $k$. This lower bound is tight because, with slight modifications, Scheffler's algorithm runs in $2^{pw\log pw+O(pw)}\cdot n$ time also for directed graphs.

0.26

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
similarity 0.65
Abstract · v2: Added a deterministic almost-linear-time incremental SSSP algorithm with efficient approximate path reporting

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

0.21

Size-Sensitive Padded Decompositions for Faster Deterministic Negative-Weight Shortest Paths

cs.DS ·2026-09-04 ·Khoi Duong
similarity 0.65
Abstract · v2 improves on v1 by log log n

We give a deterministic algorithm for single-source shortest paths in directed graphs with integral edge weights at least $-W$ that runs in time $$O((m+n\log\log n)\log^2 n \log(nW)).$$ This improves the previous fastest deterministic bound of Li by a factor of $\log n$.

0.18