How Does the Floyd-Warshall Algorithm Find Shortest Paths?

The Floyd-Warshall algorithm is a classical dynamic programming method used to find the shortest paths between all pairs of vertices in a weighted, directed graph. It works by systematically considering every vertex as a potential intermediate stop along a path and updating a distance matrix until the optimal routes are found. Unlike single-source algorithms such as Dijkstra's, it handles negative edge weights as long as no negative-weight cycles exist.

The Core Dynamic Programming Idea

In a graph \(G = (V, E)\) with \(n = |V|\) vertices numbered from \(1\) to \(n\), the algorithm defines a subproblem based on which intermediate vertices are allowed. Let \(d^{(k)}_{ij}\) represent the length of the shortest path from vertex \(i\) to vertex \(j\) such that all intermediate vertices on the path belong to the set \(\{1, 2, \dots, k\}\).

When \(k = 0\), no intermediate vertices are allowed, so the shortest path is simply the direct edge between \(i\) and \(j\):

\[d^{(0)}_{ij} = \begin{cases} 0 & \text{if } i = j \\ w(i, j) & \text{if } (i, j) \in E \\ \infty & \text{otherwise} \end{cases}\]

Here, \(w(i, j)\) denotes the weight of the directed edge from \(i\) to \(j\).

The Recurrence Relation

To compute \(d^{(k)}_{ij}\) for \(k \ge 1\), the algorithm compares two possibilities for the shortest path from \(i\) to \(j\) using intermediate vertices from \(\{1, \dots, k\}\):

  1. The path does not pass through vertex \(k\), meaning all intermediate vertices are in \(\{1, \dots, k-1\}\), and the length is \(d^{(k-1)}_{ij}\).
  2. The path does pass through vertex \(k\), splitting into a shortest path from \(i\) to \(k\) and a shortest path from \(k\) to \(j\), both using only intermediate vertices in \(\{1, \dots, k-1\}\).

This yields the recurrence relation:

\[d^{(k)}_{ij} = \min\left(d^{(k-1)}_{ij},\; d^{(k-1)}_{ik} + d^{(k-1)}_{kj}\right)\]

Step-by-Step Execution

In classical computing, the algorithm is implemented using three nested loops over an \(n \times n\) matrix \(D\) initialized to \(d^{(0)}\):

  1. Outer loop (\(k\) from \(1\) to \(n\)): Selects the current intermediate vertex \(k\).
  2. Middle loop (\(i\) from \(1\) to \(n\)): Selects the starting vertex \(i\).
  3. Inner loop (\(j\) from \(1\) to \(n\)): Selects the destination vertex \(j\) and updates \(D[i][j] = \min(D[i][j], D[i][k] + D[k][j])\).

Because \(D[i][k]\) and \(D[k][j]\) do not depend on \(D[i][j]\) within the same \(k\) iteration (assuming no negative-weight cycles), the updates can be performed in-place on a single \(n \times n\) matrix rather than storing \(n\) separate matrices.

Time and Space Complexity

The three nested loops each run \(n\) times, giving a time complexity of \(\mathcal{O}(|V|^3)\). Because the matrix can be updated in-place, the space complexity is \(\mathcal{O}(|V|^2)\). This makes the Floyd-Warshall algorithm particularly effective for dense graphs where \(|E|\) is close to \(|V|^2\).

Detecting Negative-Weight Cycles

After the algorithm completes, any negative value on the main diagonal (\(D[i][i] < 0\)) indicates that vertex \(i\) is part of a negative-weight cycle. In such cases, shortest paths involving that cycle are undefined because the total path weight can be reduced indefinitely.