Shortest Path(Directed graphs)

From Algorithm Wiki
Jump to navigation Jump to search

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