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

Parameters

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

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 5 of 5 algorithms


Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan 1984; Fredman & Tarjan 1987)	1984	$O(E + V \log V)$	$O(V)$
Gabow's algorithm	1983	$O(E \log L/\log(2+(E/V)))$	$O(V+E)$
Dijkstra's algorithm with binary heap (Johnson 1977)	1977	$O((E + V) \log V)$	$O(V)$
Bellman–Ford algorithm (Dantzig 1960)	1960	$O(V^2 \log V)$	$O(E)$
Dijkstra's algorithm with list (Whiting & Hillier 1960)	1960	$O(V^2)$	$O(V)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms