Shortest path problem: Difference between revisions

Revision as of 19:19, 24 January 2024

Revision as of 00:05, 15 March 2024

Line 111:

! Weights !! Algorithm !! Time complexity !! Author

|-

| <math>\mathbb{R}</math> || || ''<math>O''(''V''<sup> ^2 E L)
</supmath>''EL'') || {{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''&nbsp;('' E''&nbsp; +&nbsp; V \log&nbsp;'' V'')) </math>|| {{harvnb|Johnson|1977}}

|-

| <math>\mathbb{R}</math> || [[Johnson's algorithm|Johnson-Dijkstra]] with [[Fibonacci heap]] || ''<math>O''(''V''&nbsp;('' E''&nbsp; +&nbsp; V \log&nbsp;'' V'')) </math>|| {{harvnb|Fredman|Tarjan|1984}}, {{harvnb|Fredman|Tarjan|1987}}, adapted after {{harvnb|Johnson|1977}}

|-

| <math>\mathbb{NZ}</math> || [[Johnson's algorithm|Johnson's technique]] applied to Dial's algorithm<ref name="dial69" /> || ''<math>O''(''V''&nbsp;(''E''&nbsp;+&nbsp;''L'')) </math>|| {{harvnb|Dial|1969}}, adapted after {{harvnb|Johnson|1977}}

|-

|<math>\mathbb{NZ}</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|Ref=https://doi.org/10.1137/1.9781611974782.48}}

|-

|<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|Ref=https://doi.org/10.1109/FOCS46700.2020.00018}}

|-

|<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, Saranurak, Sidford, Song, Wang|2020|Ref=https://doi.org/10.1109/FOCS46700.2020.00090}}

|-

|<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|2023|4=|Ref=https://arxiv.org/abs/2311.02520}}

|}

{{incomplete list|date=December 2012}}

Line 133 ⟶ 154:

! Weights !! Algorithm !! Time complexity !! Author

|-

| <math>\mathbb{Z}</math> || Andrew V. Goldberg || <math>O(E\sqrt{V}\log{N})</math> ||Andrew V. Goldberg

|}