Editing Shortest path problem (section)

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