Nonnegative Weights (Shortest Path (Directed Graphs))

From Algorithm Wiki
Jump to navigation Jump to search


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. Here, the weights are restricted to be nonnegative.

Related Problems

Generalizations: general weights

Subproblem: Nonnegative Integer Weights

Related: General Weights, Second Shortest Simple Path, st-Shortest Path, 1-sensitive (3/2)-approximate ss-shortest paths, 2-sensitive (7/5)-approximate st-shortest paths, 1-sensitive decremental st-shortest paths, 2-sensitive decremental st-shortest paths, Replacement Paths Problem


$V$: number of vertices

$E$: number of edges

$L$: maximum absolute value of edge cost

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Bellman–Ford algorithm (Dantzig ) 1960 $O(V^{2} \log V)$ $O(E)$ (total) Exact Deterministic Time
Dijkstra's algorithm with list (Whiting & Hillier ) 1960 $O(V^{2})$ $O(V)$ Exact Deterministic Time
Dijkstra's algorithm with binary heap (Johnson ) 1977 $O((E + V) \log V)$ $O(V)$ Exact Deterministic Time
Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan ; Fredman & Tarjan 1987) 1984 $O(E + V \log V)$ $O(V)$ Exact Deterministic Time
Gabow's algorithm 1983 $O(E \log L/\log({2}+(E/V)))$ $O(V+E)$? Exact Deterministic Time

Time Complexity Graph

Shortest Path (Directed Graphs) - Nonnegative Weights - Time.png