Editing Shortest path problem (section)

==All-pairs shortest paths==
The all-pairs shortest path problem finds the shortest paths between every pair of vertices {{mvar|v}}, {{mvar|v'}} in the graph.  The all-pairs shortest paths problem for unweighted directed graphs was introduced by {{harvtxt|Shimbel|1953}}, who observed that it could be solved by a linear number of matrix multiplications that takes a total time of {{math|''O''(''V''<sup>4</sup>)}}.

===Undirected graph===
{| class=wikitable
! Weights !! Time complexity !! Algorithm
|-
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''V''<sup>3</sup>)}} || [[Floyd–Warshall algorithm]]
|-
| <math>\{1, \infty\}</math> || <math>O(V^\omega \log V)</math> || [[Seidel's algorithm]] (expected running time)
|-
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log V)^{1/2}})</math> || {{harvnb|Williams|2014}}
|-
| <math>\mathbb{R}</math><sub>+</sub> || {{math|''O''(''EV''&nbsp;log&nbsp;α(''E'',''V''))}} || {{harvnb|Pettie|Ramachandran|2002}}
|-
| <math>\mathbb{N}</math> || {{math|''O''(''EV'')}} || {{harvnb|Thorup|1999}} applied to every vertex (requires constant-time multiplication).
|}

===Directed graph===
{| class=wikitable
! Weights !! Time complexity !! Algorithm
|-
| <math>\mathbb{R}</math> (no negative cycles) || <math>O(V^3)</math> || [[Floyd–Warshall algorithm]]
|-
| <math>\mathbb{N}</math> || <math>O(V^3/2^{\Omega(\log V)^{1/2}})</math> || {{harvnb|Williams|2014}}
|-
| <math>\mathbb{R}</math> (no negative cycles) || <math>O(V^{2.5}\log^2{V})</math> || [[Grover's algorithm|Quantum search]]<ref>{{Cite arXiv |last1=Dürr |first1=C. |last2=Høyer |first2=P. |date=1996-07-18 |title=A Quantum Algorithm for Finding the Minimum |eprint=quant-ph/9607014 }}</ref><ref>{{Cite arXiv |last1=Nayebi |first1=Aran |last2=Williams |first2=V. V. |date=2014-10-22 |title=Quantum algorithms for shortest paths problems in structured instances |class=quant-ph |eprint=1410.6220}}</ref>
|-
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;''V'')}} || [[Johnson's algorithm|Johnson–Dijkstra]]
|-
| <math>\mathbb{R}</math> (no negative cycles) || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb|Pettie|2004}}
|-
| <math>\mathbb{N}</math> || {{math|''O''(''EV''&nbsp;+&nbsp;''V''<sup>2</sup>&nbsp;log&nbsp;log&nbsp;''V'')}} || {{harvnb|Hagerup|2000}}
|}