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

From Algorithm Wiki
Jump to navigation Jump to search
(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...")
 
Line 4: Line 4:


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


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

Revision as of 08:08, 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

[[File:Shortest_Path (Directed_graphs)StepChart.png|350px]]

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn