Difference between revisions of "Shortest Path(Directed graphs)"

From Algorithm Wiki
Jump to navigation Jump to search
Line 22: Line 22:
|-
|-
| rowspan="1" | Cubic
| rowspan="1" | Cubic
|
| [https://www.rand.org/pubs/papers/P923.html Bellman–Ford algorithm (Ford 1956) (1956)]
 
[https://pubsonline.informs.org/doi/10.1287/mnsc.6.2.187 Bellman–Ford algorithm (Dantzig 1960) (1960)]
|
|
|-
|-
| rowspan="1" | Quadratic
| rowspan="1" | Quadratic
|
| [https://ci.nii.ac.jp/naid/10015375086/ Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959) (1959)]
 
[https://www.jstor.org/stable/3007178?seq=1#page_scan_tab_contents Dijkstra's algorithm with list (Whiting & Hillier 1960) (1960)]
 
[https://dl.acm.org/citation.cfm?id=321993 Dijkstra's algorithm with binary heap (Johnson 1977) (1977)]
 
[https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987) (1984)]
 
[https://link.springer.com/chapter/10.1007/978-3-540-27810-8_33 Thorup's algorithm (2004)]
|
|
|-
|-
| rowspan="1" | nlogn
| rowspan="1" | nlogn
|
| [https://dl.acm.org/doi/10.1145/321992.321993 Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (1981)]
|
|
|-
|-
| rowspan="1" | Linear
| rowspan="1" | Linear
|
| [ Gabow's algorithm (1983)]
 
[ Gabow Ahuja algorithm (1990)]
|
|
|-
|-

Revision as of 13:53, 15 September 2021

Problem Description

the shortest path problem is the problem of finding a path between two vertices

(or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Bounds Chart

Shortest Path (Directed graphs)BoundsChart.png

Step Chart

Shortest Path (Directed graphs)StepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic Bellman–Ford algorithm (Ford 1956) (1956)

Bellman–Ford algorithm (Dantzig 1960) (1960)

Quadratic Bellman–Ford algorithm (Shimbel 1955; Bellman 1958; Moore 1959) (1959)

Dijkstra's algorithm with list (Whiting & Hillier 1960) (1960)

Dijkstra's algorithm with binary heap (Johnson 1977) (1977)

Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987) (1984)

Thorup's algorithm (2004)

nlogn Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983) (1981)
Linear [ Gabow's algorithm (1983)]

[ Gabow Ahuja algorithm (1990)]

logn