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

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² logV)$	$O(E)$ (total)	Exact	Deterministic	Time
Dijkstra's algorithm with list (Whiting & Hillier )	1960	$O( V² )$	$O(V)$ auxiliary	Exact	Deterministic	Time
Dijkstra's algorithm with binary heap (Johnson )	1977	$O((E + V) log V)$	$O(V)$ auxiliary	Exact	Deterministic	Time
Dijkstra's algorithm with Fibonacci heap (Fredman & Tarjan ; Fredman & Tarjan 1987)	1984	$O(E + V log V)$	$O(V)$ auxiliary	Exact	Deterministic	Time
Gabow's algorithm	1983	$O(E logL/log({2}+(E/V)))$	$O(V+E)$?	Exact	Deterministic	Time

Time Complexity graph

Space Complexity graph

Pareto Decades graph

References/Citation

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