Nonnegative Integer Weights (Shortest Path (Directed Graphs))

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. 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

Parameters

$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

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity Graph

Error creating thumbnail: Unable to save thumbnail to destination

Time-Space Tradeoff

Error creating thumbnail: Unable to save thumbnail to destination

References/Citation

https://dl-acm-org.ezproxy.canberra.edu.au/doi/10.1016/j.jcss.2004.04.003