Nonnegative Integer Weights

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.

Parameters

$V$ : number of vertices
$E$ : number of edges
$L$ : maximum absolute value of edge cost

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Thorup's algorithm	2004	$O(E + V \min(\log \log V, \log \log L))$	$O(V)$ ("linear-space queue")
Gabow Ahuja Algorithm	1990	$O(E + V \sqrt{\log(L)} )$	$O(E + \log C)$
Dijkstra's algorithm with Fibonacci heap (Johnson 1981; Karlsson & Poblete 1983)	1981	$O(E \log \log L)$	$O(V+L)$
Dial's Algorithm	1969	O(E+LV)	O(V+L)

Reductions Table

Insuffient Data to display table

Other relevant algorithms