Difference between revisions of "Shortest Path(Directed graphs)"
Jump to navigation
Jump to search
Yashsherry (talk  contribs) (Created page with "== 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 constit...") 
Yashsherry (talk  contribs) 

(5 intermediate revisions by the same user not shown)  
Line 1:  Line 1:  
== Problem Description==  == Problem Description==  
The shortest path problem involves finding the shortest path between two vertices (or nodes) in a graph. Algorithms such as the FloydWarshall algorithm and different variations of Dijkstra's algorithm are used to find solutions to the shortest path problem.  
Applications of the shortest path problem include those in road networks, logistics, communications, electronic design, power grid contingency analysis, and community detection.  
== Bounds Chart ==  == Bounds Chart ==  
[[File:  [[File:Shortest_Path_(Directed_graphs)BoundsChart.png1050px]]  
(Directed_graphs)BoundsChart.png  
== Step Chart ==  == Step Chart ==  
[[File:  [[File:Shortest_Path_(Directed_graphs)StepChart.png1050px]]  
(Directed_graphs)StepChart.png  
== Improvement Table ==  == Improvement Table ==  
Line 24:  Line 23:  
    
 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/9783540278108_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)]  
    
   
Latest revision as of 13:54, 15 September 2021
Problem Description
The shortest path problem involves finding the shortest path between two vertices (or nodes) in a graph. Algorithms such as the FloydWarshall algorithm and different variations of Dijkstra's algorithm are used to find solutions to the shortest path problem.
Applications of the shortest path problem include those in road networks, logistics, communications, electronic design, power grid contingency analysis, and community detection.
Bounds Chart
Step Chart
Improvement Table
Complexity Classes  Algorithm Paper Links  Lower Bounds Paper Links 

Exp/Factorial  
Polynomial > 3  
Cubic  Bellman–Ford algorithm (Ford 1956) (1956)  
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) 

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

logn 