Editing Shortest path problem (section)

===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}}