Shortest Paths

Shortest-path algorithms extend BFS to weighted edges. Dijkstra pops the closest unsettled vertex from a priority queue, and since no edge is negative, nothing found later can beat a distance once it's been popped.

Algorithm	Weights	Typical use
Dijkstra	Non-negative	One source, sparse graph
Bellman-Ford	Any, flags negative cycles	One source, negative edges
Floyd-Warshall	Any, no negative cycles	Every pair, small $n$

The usual slip is running Dijkstra on a graph with negative edges, where a popped distance can still improve and the answer comes out quietly wrong. That's Bellman-Ford's job, at a higher cost. Dijkstra doesn't need sums either, only a path cost that never shrinks as the path grows, so the largest step along a path works too. With every weight equal to one, plain BFS already is Dijkstra.

Approach	Time	Extra space
Dijkstra with a binary heap	$O((V + E) \log V)$	$O(V + E)$
Bellman-Ford	$O(VE)$	$O(V)$
Floyd-Warshall	$O(V^3)$	$O(V^2)$

Use these when edges have costs and the question asks for the cheapest route from one source, the cheapest route between every pair of vertices, or whether a cycle lets you improve a score forever.

The problems below start with Dijkstra on an edge list, move through Dijkstra on a grid where a path costs its steepest step, then Bellman-Ford with cycle detection, and end with Floyd-Warshall answering queries between every pair.