Nonnegative Weights

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.

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

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

Error creating thumbnail: Unable to save thumbnail to destination

References/Citation

https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf