pith. sign in

arxiv: 2607.02443 · v1 · pith:VXCYBE3Anew · submitted 2026-07-02 · 💻 cs.DS

Improved Approximation Algorithms for n-Pairs Shortest Paths

Avi Kadria , Liam Roditty , Virginia Vassilevska Williams This is my paper

Pith reviewed 2026-07-03 03:37 UTC · model grok-4.3

classification 💻 cs.DS
keywords approximation algorithmsshortest pathsn-pairs shortest pathsweighted graphsheavy-edge techniquegraph algorithmsmultiplicative approximation
0
0 comments X

The pith

A heavy-edge technique yields the first (2 - α)k-approximation for n-pairs shortest paths in weighted graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops the first algorithm achieving a (2 - α)k-approximation for the n-Pairs Shortest Paths problem in weighted undirected graphs, running in Õ(mn^{1/k} + n^{1 + 2/k}) time. It specifically gives a 1.622k-approximation that improves on the prior (2k - 3) bound. The central innovation is the heavy-edge technique, which converts approximations that depend on the heaviest edge weight into purely multiplicative ones. A reader would care because this provides better distance estimates for many pairs in networks without depending on particular edge weights.

Core claim

We present the first algorithm for the n-Pairs Shortest Paths problem in weighted undirected graphs that achieves a (2 - α)k-approximation, for constant α > 0, that runs in Õ(mn^{1/k} + n^{1 + 2/k}) time. Specifically, we present a 1.622k-approximation, improving upon the (2k - 3)-approximation of Chechik, Hoch, and Lifshitz. Our main technical contribution is the new heavy-edge technique that transforms an algorithm with an approximation guarantee that depends on W_uv into one with purely multiplicative approximation.

What carries the argument

the heavy-edge technique, which transforms an algorithm with an approximation guarantee that depends on the weight of the heaviest edge on the shortest path (W_uv) into an algorithm with a purely multiplicative approximation that does not depend on W_uv

If this is right

  • Improved approximation algorithms for unweighted graphs and dense weighted graphs
  • Affirmative answer to the open question posed by Chechik et al. for non-super-sparse graphs
  • Better time-approximation tradeoffs than previous results

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The heavy-edge technique could be applied to other graph distance problems involving variable edge weights
  • This may enable more efficient solutions for applications like transportation networks or social graphs requiring many pair distances
  • Further improvements to the constant factor in the approximation might be possible by refining the technique

Load-bearing premise

The heavy-edge technique successfully converts an algorithm whose approximation depends on W_uv, the heaviest edge weight on the shortest path, into one with a purely multiplicative guarantee independent of W_uv, without increasing the asymptotic time complexity.

What would settle it

An instance of the n-Pairs Shortest Paths problem where the heavy-edge technique fails to produce a purely multiplicative approximation or exceeds the 1.622k factor while keeping the stated runtime.

Figures

Figures reproduced from arXiv: 2607.02443 by Avi Kadria, Liam Roditty, Virginia Vassilevska Williams.

Figure 1
Figure 1. Figure 1: The three cases of Lemma 6. i = max{j | hj (τ ) ≤ j · t}. By combining this bound with the fact that ˆd(u, v) ≤ (4i + 6)t we get that: ˆd(u, v) ≤ min(4k − 2i − 4, 4i + 6)t ≤ (⌈4k/3⌉ − 1)2t, as required. Therefore, to complete the proof of the lemma, it remains to show that in cases 2 and 3, we have that ˆd(u, v) ≤ (4i + 6)t and min(hi+1(u), hi+1(v)) ≤ (i + 1)t. To prove cases 2 and 3, we first prove the fo… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of P(u, v), where (τu, τv) ∈ P(u, v) and d(u, τu) ≤ d(u, v)/2, d(u, τv) > d(u, v)/2. Next, we present the main result of this paper: the first truly (2 − α)k, for α > 0, approximation n-PSP algorithm for weighted undirected graphs with non-negative real edge weights. We prove: Reminder of Theorem 1. Let G = (V, E, ℓ) be a weighted undirected graph, where ℓ : E → R≥0, and let k ≥ 4 be an intege… view at source ↗
Figure 3
Figure 3. Figure 3: The two cases of Claim 8.1. t ≥ (1/2 + c)δ. ju = min(i | pi(τ ) ∈ B(u)), jv = min(i | pi(v) ∈ B(τv) ∨ pi(τv) ∈ B(v)). Since pju (τ ) ∈ B(u) and pjv (v) ∈ B(v), in the final loop of the algorithm there is an iteration in which w = pju (τ ) and z = pjv (v). Therefore: ˆd(u, v) ≤ d(u, pju (τ )) + H(pju (τ ), pjv (v)) + hjv (v) 4 ≤ d(u, pju (τ )) + (hju (τ ) + ℓ(τ, τv) + d(τv, pjv (v))) + hjv (v) △ ≤ d(u, τ ) … view at source ↗
read the original abstract

Let $G = (V, E)$ be a graph with $n = |V|$ nodes and $m = |E|$ edges. The $t$-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between $t$ prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where $t = \Theta(n)$: the $n$-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the $n$-Pairs Shortest Paths problem in \textit{weighted} undirected graphs that achieves a $(2 - \alpha)k$-approximation, for constant $\alpha > 0$, that runs in $\tilde{O}(mn^{1/k} + n^{1 + 2/k})$ time. Specifically, we present a $1.622k$-approximation, improving upon the $(2k - 3)$-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard \etal~and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new \textit{heavy-edge} technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on $W_{uv}$, the weight of the heaviest edge on the shortest path between $u$ and $v$, into an algorithm with purely multiplicative approximation that does not depend on $W_{uv}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to introduce a new heavy-edge technique that converts an algorithm whose approximation ratio depends on W_uv (the heaviest edge weight on the shortest path between u and v) into one achieving a purely multiplicative (2 - α)k-approximation (specifically 1.622k) for the n-Pairs Shortest Paths problem on weighted undirected graphs. The algorithm runs in Õ(m n^{1/k} + n^{1 + 2/k}) time and improves on the (2k - 3)-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for non-super-sparse graphs; additional improved tradeoffs are given for unweighted graphs and dense weighted graphs.

Significance. If the heavy-edge technique holds, the result answers an open question from prior work by providing the first (2 - α)k-approximation for this regime and may have broader applicability to other distance-approximation problems where weight-dependent ratios arise. The explicit improvement over (2k - 3) and the stated time bound constitute a concrete advance in the area.

major comments (2)
  1. [Main technical contribution (heavy-edge technique description)] The central claim rests on the heavy-edge technique successfully producing a W_uv-independent multiplicative guarantee while preserving the Õ(m n^{1/k} + n^{1 + 2/k}) time bound. The abstract describes the transformation but does not supply the explicit construction, the derivation of the constant yielding 1.622 (i.e., the precise value of α), or the analysis showing that the reduction does not introduce additional factors depending on the maximum edge weight; a dedicated section or theorem with the full proof is required to confirm the claim.
  2. [Introduction / comparison with Chechik et al. [SODA'25]] The improvement is stated to hold for graphs that are not super-sparse, yet the precise threshold on m (relative to n and k) at which the new bound strictly dominates the prior (2k - 3) result is not quantified in the abstract or comparison statements; this affects the scope of the claimed resolution of the open question.
minor comments (2)
  1. [Abstract and preliminaries] The notation ilde{O} is used without explicit definition; confirm it hides only polylog(n) factors and state this clearly in the preliminaries.
  2. [Heavy-edge technique section] Ensure that the definition of W_uv (heaviest edge on the shortest path) is restated verbatim in the section introducing the heavy-edge technique for reader convenience.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address each major comment below and will revise the manuscript to improve clarity and completeness.

read point-by-point responses

  1. Referee: [Main technical contribution (heavy-edge technique description)] The central claim rests on the heavy-edge technique successfully producing a W_uv-independent multiplicative guarantee while preserving the Õ(m n^{1/k} + n^{1 + 2/k}) time bound. The abstract describes the transformation but does not supply the explicit construction, the derivation of the constant yielding 1.622 (i.e., the precise value of α), or the analysis showing that the reduction does not introduce additional factors depending on the maximum edge weight; a dedicated section or theorem with the full proof is required to confirm the claim.

    Authors: The manuscript contains the full details of the heavy-edge technique, including the explicit construction, the derivation of α (yielding the 1.622 factor), and the analysis establishing W_uv-independence, in the technical sections following the introduction. To make this more prominent as requested, we will add a dedicated theorem statement (with a proof sketch) early in the paper that summarizes the transformation and confirms preservation of the time bound. This addresses the concern without changing any technical claims. revision: yes

  2. Referee: [Introduction / comparison with Chechik et al. [SODA'25]] The improvement is stated to hold for graphs that are not super-sparse, yet the precise threshold on m (relative to n and k) at which the new bound strictly dominates the prior (2k - 3) result is not quantified in the abstract or comparison statements; this affects the scope of the claimed resolution of the open question.

    Authors: We agree that an explicit quantification of the regime (in terms of m relative to n and k) would clarify the scope. In the revision we will add this threshold to the abstract and introduction, based on comparing the running times and approximation ratios of the two algorithms. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new technique independent of inputs

full rationale

The paper's core contribution is a new heavy-edge technique that converts a W_uv-dependent approximation algorithm into one with a purely multiplicative (2-α)k guarantee while preserving the runtime bound. This is presented as an algorithmic transformation, not a definitional equivalence or fitted parameter renamed as prediction. The improvement over Chechik et al. [SODA'25] (different authors) is stated as resolving an open question via this technique. No self-citation is load-bearing for the central claim, no ansatz is smuggled, and no equation reduces to its own input by construction. The derivation chain is self-contained against external algorithmic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The contribution is algorithmic and relies on standard graph-theoretic properties rather than new fitted parameters or postulated entities.

axioms (1)
  • standard math Standard definitions and properties of shortest paths in undirected weighted graphs
    The paper invokes basic facts about shortest paths and graph distances that are standard in the field.

pith-pipeline@v0.9.1-grok · 5904 in / 1273 out tokens · 35144 ms · 2026-07-03T03:37:52.619332+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

48 extracted references · 36 canonical work pages · 2 internal anchors

  1. [1]

    Compact routing schemes , booktitle =

    Mikkel Thorup and Uri Zwick , editor =. Compact routing schemes , booktitle =. 2001 , url =. doi:10.1145/378580.378581 , timestamp =

    work page doi:10.1145/378580.378581 2001

  2. [2]

    Mikkel Thorup and Uri Zwick , title =. J. 2005 , url =. doi:10.1145/1044731.1044732 , timestamp =

    work page doi:10.1145/1044731.1044732 2005

  3. [3]

    Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation , booktitle =

    Alina Harbuzova and Ce Jin and Virginia Vassilevska Williams and Zixuan Xu , editor =. Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.166 , timestamp =

    work page doi:10.1137/1.9781611977912.166 2024

  4. [4]

    Faster Approximate Distance Queries and Compact Routing in Sparse Graphs

    Rachit Agarwal and Brighten Godfrey and Sariel Har. Faster Approximate Distance Queries and Compact Routing in Sparse Graphs , journal =. 2012 , url =. 1201.2703 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  5. [5]

    Distance Oracles for Stretch Less Than 2 , booktitle =

    Rachit Agarwal and Philip Brighten Godfrey , editor =. Distance Oracles for Stretch Less Than 2 , booktitle =. 2013 , url =. doi:10.1137/1.9781611973105.38 , timestamp =

    work page doi:10.1137/1.9781611973105.38 2013

  6. [6]

    The Space-Stretch-Time Tradeoff in Distance Oracles , booktitle =

    Rachit Agarwal , editor =. The Space-Stretch-Time Tradeoff in Distance Oracles , booktitle =. 2014 , url =. doi:10.1007/978-3-662-44777-2\_5 , timestamp =

    work page doi:10.1007/978-3-662-44777-2 2014

  7. [7]

    Distance Oracles beyond the Thorup-Zwick Bound , journal =

    Mihai P. Distance Oracles beyond the Thorup-Zwick Bound , journal =. 2014 , url =. doi:10.1137/11084128X , timestamp =

    work page doi:10.1137/11084128x 2014

  8. [8]

    Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs , journal =

    Davide Bil. Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs , journal =. 2023 , url =. doi:10.48550/ARXIV.2307.11677 , eprinttype =. 2307.11677 , timestamp =

    work page doi:10.48550/arxiv.2307.11677 2023

  9. [9]

    A New Infinity of Distance Oracles for Sparse Graphs , booktitle =

    Mihai P. A New Infinity of Distance Oracles for Sparse Graphs , booktitle =. 2012 , url =. doi:10.1109/FOCS.2012.44 , timestamp =

    work page doi:10.1109/focs.2012.44 2012

  10. [10]

    Deterministic Constructions of Approximate Distance Oracles and Spanners , booktitle =

    Liam Roditty and Mikkel Thorup and Uri Zwick , editor =. Deterministic Constructions of Approximate Distance Oracles and Spanners , booktitle =. 2005 , url =. doi:10.1007/11523468\_22 , timestamp =

    work page doi:10.1007/11523468 2005

  11. [11]

    Proceedings of the Seventeenth Annual

    Mikkel Thorup and Uri Zwick , title =. Proceedings of the Seventeenth Annual. 2006 , url =

    2006

  12. [12]

    2010 , url =

    Surender Baswana and Telikepalli Kavitha and Kurt Mehlhorn and Seth Pettie , title =. 2010 , url =. doi:10.1145/1868237.1868242 , timestamp =

    work page doi:10.1145/1868237.1868242 2010

  13. [13]

    2021 , issue_date =

    Bodwin, Greg and Williams, Virginia Vassilevska , title =. 2021 , issue_date =. doi:10.1145/3490147 , journal =

    work page doi:10.1145/3490147 2021

  14. [14]

    Bypassing Erd

    Merav Parter , editor =. Bypassing Erd. Automata, Languages, and Programming - 41st International Colloquium,. 2014 , url =. doi:10.1007/978-3-662-43951-7\_49 , timestamp =

    work page doi:10.1007/978-3-662-43951-7 2014

  15. [15]

    New Additive Spanners , booktitle =

    Shiri Chechik , editor =. New Additive Spanners , booktitle =. 2013 , url =. doi:10.1137/1.9781611973105.36 , timestamp =

    work page doi:10.1137/1.9781611973105.36 2013

  16. [16]

    Amir Abboud and Greg Bodwin , title =. J. 2017 , url =. doi:10.1145/3088511 , timestamp =

    work page doi:10.1145/3088511 2017

  17. [17]

    2018 , url =

    Amir Abboud and Greg Bodwin and Seth Pettie , title =. 2018 , url =. doi:10.1137/16M1105815 , timestamp =

    work page doi:10.1137/16m1105815 2018

  18. [18]

    2004 , url =

    Michael Elkin and David Peleg , title =. 2004 , url =. doi:10.1137/S0097539701393384 , timestamp =

    work page doi:10.1137/s0097539701393384 2004

  19. [19]

    On Approximate Distance Labels and Routing Schemes with Affine Stretch , booktitle =

    Ittai Abraham and Cyril Gavoille , editor =. On Approximate Distance Labels and Routing Schemes with Affine Stretch , booktitle =. 2011 , url =. doi:10.1007/978-3-642-24100-0\_39 , timestamp =

    work page doi:10.1007/978-3-642-24100-0 2011

  20. [20]

    Approximate distance oracles with constant query time , booktitle =

    Shiri Chechik , editor =. Approximate distance oracles with constant query time , booktitle =. 2014 , url =. doi:10.1145/2591796.2591801 , timestamp =

    work page doi:10.1145/2591796.2591801 2014

  21. [21]

    Approximate Distance Oracles with Improved Bounds , booktitle =

    Shiri Chechik , editor =. Approximate Distance Oracles with Improved Bounds , booktitle =. 2015 , url =. doi:10.1145/2746539.2746562 , timestamp =

    work page doi:10.1145/2746539.2746562 2015

  22. [22]

    2010 , url =

    Surender Baswana and Telikepalli Kavitha , title =. 2010 , url =. doi:10.1137/080737174 , timestamp =

    work page doi:10.1137/080737174 2010

  23. [23]

    Approximate distance oracles with improved preprocessing time , booktitle =

    Christian Wulff. Approximate distance oracles with improved preprocessing time , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.18 , timestamp =

    work page doi:10.1137/1.9781611973099.18 2012

  24. [24]

    Space-efficient path-reporting approximate distance oracles , journal =

    Michael Elkin and Ofer Neiman and Christian Wulff. Space-efficient path-reporting approximate distance oracles , journal =. 2016 , url =. doi:10.1016/J.TCS.2016.07.038 , timestamp =

    work page doi:10.1016/j.tcs.2016.07.038 2016

  25. [25]

    2016 , url =

    Michael Elkin and Seth Pettie , title =. 2016 , url =. doi:10.1145/2888397 , timestamp =

    work page doi:10.1145/2888397 2016

  26. [26]

    47th Annual

    Manor Mendel and Assaf Naor , title =. 47th Annual. 2006 , url =. doi:10.1109/FOCS.2006.65 , timestamp =

    work page doi:10.1109/focs.2006.65 2006

  27. [27]

    Michael Elkin and Idan Shabat , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00141 , timestamp =

    work page doi:10.1109/focs57990.2023.00141 2023

  28. [28]

    Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size , booktitle =

    Shiri Chechik and Tianyi Zhang , editor =. Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size , booktitle =. 2024 , url =. doi:10.4230/LIPICS.ICALP.2024.42 , timestamp =

    work page doi:10.4230/lipics.icalp.2024.42 2024

  29. [29]

    Improved girth approximation in weighted undirected graphs , booktitle =

    Avi Kadria and Liam Roditty and Aaron Sidford and Virginia Vassilevska Williams and Uri Zwick , editor =. Improved girth approximation in weighted undirected graphs , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH85 , timestamp =

    work page doi:10.1137/1.9781611977554.ch85 2023

  30. [30]

    Mina Dalirrooyfard and Ce Jin and Virginia Vassilevska Williams and Nicole Wein , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00034 , timestamp =

    work page doi:10.1109/focs54457.2022.00034 2022

  31. [31]

    New Approximation Algorithms and Reductions for

    Shiri Chechik and Itay Hoch and Gur Lifshitz , editor =. New Approximation Algorithms and Reductions for. Proceedings of the 2025 Annual. 2025 , url =. doi:10.1137/1.9781611978322.177 , timestamp =

    work page doi:10.1137/1.9781611978322.177 2025

  32. [32]

    Random Struct

    Surender Baswana and Sandeep Sen , title =. Random Struct. Algorithms , volume =. 2007 , url =. doi:10.1002/RSA.20130 , timestamp =

    work page doi:10.1002/rsa.20130 2007

  33. [33]

    2025 , eprint=

    Faster Algorithms for (2k-1) -Stretch Distance Oracles , author=. 2025 , eprint=

    2025

  34. [34]

    Aingworth and C

    D. Aingworth and C. Chekuri and P. Indyk and R. Motwani , title =. SIAM Journal on Computing , volume =. 1999 , publisher =

    1999

  35. [35]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , editor =

    Amir Abboud and Greg Bodwin , title =. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , editor =. 2018 , pages =

    2018

  36. [36]

    SIAM Journal on Discrete Mathematics , volume =

    Don Coppersmith and Michael Elkin , title =. SIAM Journal on Discrete Mathematics , volume =. 2006 , publisher =

    2006

  37. [37]

    Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond , booktitle =

    Amir Abboud and Karl Bringmann and Seri Khoury and Or Zamir , editor =. Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond , booktitle =. 2022 , url =. doi:10.1145/3519935.3520066 , timestamp =

    work page doi:10.1145/3519935.3520066 2022

  38. [38]

    Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics , booktitle =

    Amir Abboud and Karl Bringmann and Nick Fischer , editor =. Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics , booktitle =. 2023 , url =. doi:10.1145/3564246.3585240 , timestamp =

    work page doi:10.1145/3564246.3585240 2023

  39. [39]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Removing additive structure in 3sum-based reductions , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  40. [40]

    Shimon Kogan and Merav Parter , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00078 , timestamp =

    work page doi:10.1109/focs54457.2022.00078 2022

  41. [41]

    1998 , url =

    Edith Cohen , title =. 1998 , url =. doi:10.1137/S0097539794261295 , timestamp =

    work page doi:10.1137/s0097539794261295 1998

  42. [42]

    36th International Symposium on Algorithms and Computation (ISAAC 2025) , pages=

    New Approximate Distance Oracles and Their Applications , author=. 36th International Symposium on Algorithms and Computation (ISAAC 2025) , pages=. 2025 , organization=

    2025

  43. [43]

    39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022 , pages=

    Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication , author=. 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022 , pages=. 2022 , organization=

    2022

  44. [44]

    Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Multiple-source shortest paths in planar graphs , author=. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

  45. [45]

    Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Multiple source shortest paths in a genus g graph , author=. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

  46. [46]

    Journal of the ACM (JACM) , volume=

    Undirected single-source shortest paths with positive integer weights in linear time , author=. Journal of the ACM (JACM) , volume=. 1999 , publisher=

    1999

  47. [47]

    Communications of the ACM , volume=

    Negative-weight single-source shortest paths in near-linear time , author=. Communications of the ACM , volume=. 2025 , publisher=

    2025

  48. [48]

    A Survey of Shortest-Path Algorithms

    A survey of shortest-path algorithms , author=. arXiv preprint arXiv:1705.02044 , year=

    work page internal anchor Pith review Pith/arXiv arXiv