Editing Shortest path problem (section)

==Single-source shortest paths==

===Undirected graphs===
{| class=wikitable
! Weights !! [[Time complexity]] !! Author
|-
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''V<sup>2</sup>'') || {{harvnb|Dijkstra|1959}}
|-
| <math>\mathbb{R}</math><sub>+</sub>  || ''O''((''E''&nbsp;+&nbsp;''V'')&nbsp;log&nbsp;''V'') || {{harvnb|Johnson|1977}} ([[binary heap]])
|-
| <math>\mathbb{R}</math><sub>+</sub> || ''O''(''E''&nbsp;+&nbsp;''V''&nbsp;log&nbsp;''V'') || {{harvnb|Fredman|Tarjan|1984}} ([[Fibonacci heap]])
|-
| <math>\mathbb{N}</math> || ''O''(''E'') || {{harvnb|Thorup|1999}} (requires constant-time multiplication)
|-
| <math>\mathbb{R}</math><sub>+</sub> || <math>O(E\sqrt{\log V \log \log V})</math> || {{harvnb|Duan|Mao|Shu|Yin|2023}}
|}

===Unweighted graphs===
{| class=wikitable
! Algorithm !! Time complexity !! Author
|-
| [[Breadth-first search]] || ''O''(''E''&nbsp;+&nbsp;''V'') ||
|}

===Directed acyclic graphs ===
An algorithm using [[Topological sorting#Application to shortest path finding|topological sorting]] can solve the single-source shortest path problem in time {{math|Θ(''E'' + ''V'')}} in arbitrarily-weighted directed acyclic graphs.<ref>{{harvnb|Cormen|Leiserson|Rivest|Stein|2001|p=655}}</ref>

===Directed graphs with nonnegative weights===
The following table is taken from {{harvtxt|Schrijver|2004}}, with some corrections and additions.
A green background indicates an asymptotically best bound in the table; ''L'' is the maximum length (or weight) among all edges, assuming integer edge weights.
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{R}</math> || || <math>O(V^2EL)</math> || {{harvnb|Ford|1956}}
|-
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm]] || <math>O(VE)</math> || {{harvnb|Shimbel|1955}}, {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
|-
| <math>\mathbb{R}</math> || || <math>O(V^2 \log{V})</math> || {{harvnb|Dantzig|1960}}
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with list || <math>O(V^2)</math> || {{harvnb|Leyzorek|Gray|Johnson|Ladew|1957}}, {{harvnb|Dijkstra|1959}}, Minty (see {{harvnb|Pollack|Wiebenson|1960}}), {{harvnb|Whiting|Hillier|1960}}
|-
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[binary heap]] || <math> O((E+V)\log{V})</math> || {{harvnb|Johnson|1977}}
|- style="background: #d0ffd0"
| <math>\mathbb{R}</math> || [[Dijkstra's algorithm]] with [[Fibonacci heap]]||<math>O(E+V\log{V})</math> || {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}
|-
| <math>\mathbb{R}</math> || Quantum [[Dijkstra algorithm]] with adjacency list ||<math>O(\sqrt{VE}\log^2{V})</math> || Dürr et al. 2006<ref>{{Cite journal |last1=Dürr |first1=Christoph |last2=Heiligman |first2=Mark |last3=Høyer |first3=Peter |last4=Mhalla |first4=Mehdi |date=January 2006 |title=Quantum query complexity of some graph problems |journal=SIAM Journal on Computing |volume=35 |issue=6 |pages=1310–1328 |doi=10.1137/050644719 |arxiv=quant-ph/0401091 |s2cid=14253494 |issn=0097-5397}}</ref>
|-
| <math>\mathbb{N}</math> || Dial's algorithm<ref name="dial69">{{cite journal
   | last = Dial | first = Robert B.
   | title = Algorithm 360: Shortest-Path Forest with Topological Ordering [H]
   | journal = Communications of the ACM
   | volume = 12
   | issue = 11
   | pages = 632–633
   | year = 1969
   | doi = 10.1145/363269.363610
   | s2cid = 6754003
 | doi-access = free
   }}</ref> ([[Dijkstra's algorithm]] using a [[bucket queue]] with ''L'' buckets) || <math>O(E+LV)</math> || {{harvnb|Dial|1969}}
|-
|- style="background: #d0ffd0"
| || || <math>O(E\log{\log{L}})</math> || {{harvnb|Johnson|1981}}, {{harvnb|Karlsson|Poblete|1983}}
|-
| || [[Gabow's algorithm (single-source shortest paths)|Gabow's algorithm]] || <math>O(E\log_{E/V}L) </math>|| {{harvnb|Gabow|1983}}, {{harvnb|Gabow|1985}}
|- style="background: #d0ffd0"
| || || <math> O( E + V \sqrt{\log{L}})</math> || {{harvnb|Ahuja|Mehlhorn|Orlin|Tarjan|1990}}
|-
| <math>\mathbb{N}</math>|| Thorup || <math>O(E+V \log{\log{V}})</math>|| {{harvnb|Thorup|2004}}
|}
{{incomplete list|date=February 2011}}

===Directed graphs with arbitrary weights without negative cycles===
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{R}</math> || || <math>O(V^2 E L)
</math>|| {{harvnb|Ford|1956}}
|-
| <math>\mathbb{R}</math> || [[Bellman–Ford algorithm]] || <math>O(VE)</math>|| {{harvnb|Shimbel|1955}}, {{harvnb|Bellman|1958}}, {{harvnb|Moore|1959}}
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[binary heap]] || <math>O(V E + V \log V)</math>|| {{harvnb|Johnson|1977}}
|-
| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[Fibonacci heap]] || <math>O(V E + V \log V)</math>|| {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}, adapted after {{harvnb|Johnson|1977}}
|-
| <math>\mathbb{Z}</math>|| [[Johnson's algorithm|Johnson's technique]] applied to Dial's algorithm<ref name="dial69" /> || <math>O(V(E+L))</math>|| {{harvnb|Dial|1969}}, adapted after {{harvnb|Johnson|1977}}
|-
|<math>\mathbb{Z}</math>
|[[Interior-point method]] with Laplacian solver
|<math>O(E^{10/7} \log^{O(1)} V \log^{O(1)} L)</math>
|{{harvnb|Cohen|Mądry|Sankowski|Vladu|2017}}
|-
|<math>\mathbb{Z}</math>
|[[Interior-point method]] with <math>\ell_p</math> flow solver
|<math>E^{4/3 + o(1)} \log^{O(1)} L</math>
|{{harvnb|Axiotis|Mądry|Vladu|2020}}
|-
|<math>\mathbb{Z}</math>
|Robust [[interior-point method]] with sketching
|<math>O((E + V^{3/2}) \log^{O(1)} V \log^{O(1)} L)</math>
|{{harvnb|van den Brand|Lee|Nanongkai|Peng|2020}}
|-
|<math>\mathbb{Z}</math>
| <math>\ell_1</math> [[interior-point method]] with dynamic min-ratio cycle data structure
|<math>O(E^{1+o(1)} \log L)</math>
|{{harvnb|Chen|Kyng|Liu|Peng|2022}}
|-
|<math>\mathbb{Z}</math>
|Based on low-diameter decomposition
|<math>O(E \log^8 V \log L)</math>
|{{harvnb|Bernstein|Nanongkai|Wulff-Nilsen|2022}}
|-
|<math>\mathbb{R}</math>
|Hop-limited shortest paths
|<math>O(E V^{8/9} \log^{O(1)} V)</math>
|{{harvnb|Fineman|2024}}
|}
{{incomplete list|date=December 2012}}

===Directed graphs with arbitrary weights with negative cycles===
Finds a negative cycle or calculates distances to all vertices.
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{Z}</math> || || <math>O(E\sqrt{V}\log{N})</math> ||Andrew V. Goldberg
|}

===Planar graphs with nonnegative weights===
{| class=wikitable
! Weights !! Algorithm !! Time complexity !! Author
|-
| <math>\mathbb{R}_{\geq 0}</math> || || <math> O( V )</math> || {{harvnb|Henzinger|Klein|Rao|Subramanian|1997}}
|}