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

From Algorithm Wiki
Jump to navigation Jump to search
Line 4: Line 4:


== Bounds Chart ==
== Bounds Chart ==
[[File:Shortest_Path_(Directed_graphs)BoundsChart.png|350px]]
[[File:Shortest_Path_(Directed_graphs)BoundsChart.png|1050px]]


== Step Chart ==
== Step Chart ==

Revision as of 13:48, 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
Quadratic
nlogn
Linear
logn