Floyd-Warshall Algorithm

Visualize the dynamic programming approach to finding shortest paths between all pairs of vertices in a weighted graph.

Floyd-Warshall Algorithm

Concept Overview

The Floyd-Warshall algorithm is a dynamic programming approach to finding the shortest paths between all pairs of vertices in a weighted graph. Unlike Dijkstra's algorithm which finds shortest paths from a single source, Floyd-Warshall computes the optimal paths for every possible pair simultaneously. It elegantly handles graphs with positive or negative edge weights (though not negative cycles) and operates in O(V³) time complexity.

Mathematical Definition

Let G = (V, E) be a directed or undirected graph with a weight function w: E → R. We define a shortest-path estimate matrix D^(k) where d_ij^(k) represents the shortest path from vertex i to vertex j using only vertices from the set {1, 2, ..., k} as intermediate points.

Initialization:

d_ij⁽⁰⁾ = w(i, j) if (i, j) ∈ E

d_ij⁽⁰⁾ = 0 if i = j

d_ij⁽⁰⁾ = ∞ otherwise

Recursive Step:

For k from 1 to |V|:

For i from 1 to |V|:

For j from 1 to |V|:

d_ij^(k) = min(d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1))

Key Concepts

Dynamic Programming Structure

The algorithm builds the solution incrementally. At step k, it considers whether vertex k can be used as an intermediate step to shorten any existing path from i to j. If the path i → k → j is shorter than the best previously known path i → j (which uses only vertices 1 to k-1), it updates the shortest path estimate.

Negative Cycles

While Floyd-Warshall can handle negative edge weights, it assumes there are no negative-weight cycles in the graph. A negative cycle is a path where the start and end vertex are the same, and the sum of the edge weights is less than zero. If such a cycle exists, you can traverse it infinitely to achieve an arbitrarily low path cost. Floyd-Warshall can detect these cycles: if any diagonal element d_ii becomes negative, the graph contains a negative cycle.

Path Reconstruction

To actually retrieve the shortest paths (not just their lengths), we maintain a predecessor matrix Π. When we discover a shorter path through vertex k, we update π_ij to be π_kj. After completion, we can backtrack through this matrix to reconstruct the full sequence of vertices for any path.

Related Concepts

Dynamic Programming — the underlying algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems.
Dijkstra's Algorithm — a single-source shortest path algorithm that is typically faster for non-negative graphs.
Bellman-Ford Algorithm — a single-source shortest path algorithm that can handle negative weights and detect negative cycles.

Floyd-Warshall Algorithm