Nonnegative Integer 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 integers.

Related Problems

Generalizations: nonnegative weights

Related: General Weights, Nonnegative 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
Dijkstra's algorithm with Fibonacci heap (Johnson ; Karlsson & Poblete 1983) 1981 $O(E \log \log L)$ $O(V+L)$ Exact Deterministic Time & Space
Gabow Ahuja Algorithm 1990 $O(E + V*((\log(L))^{0.5}) )$ $O(E + \log C)$ Exact Deterministic Time & Space
Thorup's algorithm 2004 $O(E + V min(log log V, log log L))$ $O(V)$? ("linear-space queue") Exact Deterministic Time & Space

Time Complexity Graph

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