Dijkstra and Floyd-Warshall: Shortest Path Algorithms Guide

Dijkstra's algorithm finds the shortest path from one starting vertex to all others in a graph with non-negative edge weights. Floyd-Warshall goes further: it finds the shortest paths between every pair of vertices at once, and it can handle negative edge weights (as long as no negative cycle exists). Together they are the two fundamental shortest-path algorithms.

Shortest paths run the modern world: GPS navigation, internet packet routing and game AI all need them constantly. Which algorithm fits depends on the situation — one source or all pairs, negative weights or not.

Key Concepts

• Dijkstra's algorithm: greedy single-source shortest paths. It keeps a set of "finalised" vertices with known shortest distances, repeatedly finalising the unfinalised vertex with the smallest tentative distance and relaxing its outgoing edges.
• Relaxation: for edge u → v with weight w, if dist[u] + w is smaller than dist[v], update dist[v].
• Requirement: Dijkstra needs non-negative edge weights; a negative edge can fool its greedy choice.
• Floyd-Warshall: all-pairs shortest paths by dynamic programming — try every vertex k as an intermediate stop: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
• Negative cycles: a loop with total negative weight makes "shortest" meaningless, since looping forever keeps decreasing the cost. Floyd-Warshall allows negative weights but not negative cycles.

How It Works

Dijkstra: (1) set the start distance to 0, all others to infinity; (2) pick the unfinalised vertex with the smallest tentative distance; (3) finalise it — its distance can never improve, because any alternative route would pass through an unfinalised vertex at least as far away (this needs non-negativity); (4) relax its outgoing edges; (5) repeat until all reachable vertices are finalised. Floyd-Warshall: build a distance matrix — 0 on the diagonal, edge weights where edges exist, infinity elsewhere — then for each intermediate vertex k and each pair (i, j), check whether i → k → j beats the current i → j distance. A negative diagonal entry afterwards reveals a negative cycle.

Worked Example

Graph: S–A weight 4, S–B weight 2, B–A weight 1, A–T weight 5, B–T weight 8. Dijkstra from S: finalise S (0); relax to dist(A) = 4, dist(B) = 2. Finalise B (2): dist(A) becomes 2 + 1 = 3, dist(T) = 2 + 8 = 10. Finalise A (3): dist(T) becomes 3 + 5 = 8. Finalise T (8). Distances: S = 0, B = 2, A = 3, T = 8. The shortest S–T path is S–B–A–T costing 2 + 1 + 5 = 8 — cheaper than S–B–T at 10. Floyd-Warshall: when k = B is processed, pair (S, A) improves from 4 to 2 + 1 = 3, and the final matrix agrees with Dijkstra on every pair.

Common Misconceptions

• Dijkstra does not work with negative weights. The "finalise the smallest" step assumes no later shortcut exists; a negative edge can create one. Use Floyd-Warshall instead.
• Dijkstra computes distances to all vertices. Stopping early when the target is finalised is a valid optimisation, but the algorithm naturally computes everything.
• Floyd-Warshall is not "Dijkstra run V times". It is a different dynamic-programming method that handles negatives and is easier to code.

Real-World Applications

• GPS navigation: Dijkstra (with speed-ups) on road networks finds fastest routes.
• Internet routing: the OSPF protocol uses Dijkstra to compute routing tables.
• Currency arbitrage: negative cycles in exchange-rate graphs reveal risk-free profit loops.

Dijkstra greedily finalises one source's nearest vertices and needs non-negative weights; Floyd-Warshall improves every pair through every intermediate vertex and tolerates negatives but not negative cycles.