Dijkstra vs Bellman-Ford vs Floyd-Warshall

Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall all find shortest paths in a weighted graph, and on the topic's graph all three gave A 0, B 2, C 5, D 7 and E 8 from A. This card compares them on the axes that decide between them: which pairs each answers, which weights each accepts, what each costs, and which design strategy each is.

All three improve distances by relaxing, the test of whether going through one more edge or vertex is shorter. They differ in how they order those tests, and that order is what fixes what each can accept.

The strategy column explains the negative-edge column. Dijkstra's algorithm makes a greedy choice, settling the closest vertex, and a greedy choice is only safe when nothing later can undo it; a negative edge can. Bellman-Ford and Floyd-Warshall never commit early. Each fills a table of subproblems in the sense of Dynamic Programming: Bellman-Ford's pass k makes every path of at most k edges right, and Floyd-Warshall's round k makes every route with stops up to k right. That patience is why they accept negative edges, and why they cost more.

On a road map of 10,000 junctions and 30,000 roads, Dijkstra's algorithm does about 40,000 heap operations of about 14 steps each, Bellman-Ford up to 300 million relaxations, and Floyd-Warshall a trillion table updates.

The rule: use Dijkstra's algorithm whenever every weight is 0 or more, because it is the cheapest by far. Use Bellman-Ford when a weight can be negative or a negative cycle must be found. Use Floyd-Warshall when every pair is wanted and V is a few hundred at most, where its short code and its single table beat running another algorithm V times.