Shortest Paths

Dijkstra with lazy deletion for non-negative weights, 0-1 BFS for weights 0 and 1, Bellman-Ford for negative edges and Floyd-Warshall for all pairs on small graphs.

55 minCF 1500–20004 interactive11 problems

The problem

Each edge now has a weight (a length, a cost, a time). The length of a path is the sum of its edge weights. The shortest path problem asks for the smallest total from a source node to every other node.

Plain BFS counts edges, so it fails here: a path with 2 heavy edges can be longer than a path with 5 light ones.

Which tool to use depends on the weights:

Situation	Tool	Time
All weights equal	BFS	$O(n + m)$
Weights only 0 or 1	0-1 BFS	$O(n + m)$
Weights $\ge 0$	Dijkstra	$O((n + m) \log n)$
Negative weights possible	Bellman-Ford	$O(n \cdot m)$
All pairs, $n$ up to a few hundred	Floyd-Warshall	$O(n^3)$

1 of 9