Shortest Path(Directed graphs)

From Algorithm Wiki
Revision as of 08:03, 15 September 2021 by 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

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

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