Shortest Path Algorithm: Floyd-Warshall Algorithm

Shortest Path Algorithm: Floyd-Warshall Algorithm

Floyd-Warshall is a dynamic programming algorithm used to compute the shortest paths between all pairs of vertices in a weighted graph. Unlike Dijkstra's algorithm (which computes single-source shortest paths) or the Bellman-Ford algorithm, Floyd-Warshall can handle graphs with negative-weight edges (but not graphs containing negative-weight cycles) and finds the shortest distances between all vertices in one go.

Core Idea and Dynamic Programming State Definition

The core idea of the algorithm is: for any two vertices i and j in the graph, consider all other vertices as potential "intermediate stops." We iteratively test whether introducing an intermediate vertex k can make the path from i to j shorter.

We define a two-dimensional array dist as our dynamic programming state:

  • dist[k][i][j] represents the shortest path distance from vertex i to vertex j when considering the first k vertices (numbered 0, 1, ..., k-1) as possible intermediate vertices.

However, observation shows that state dist[k] depends only on state dist[k-1]. Therefore, we can "flatten" the three-dimensional array into a two-dimensional array through overwriting to save space. We ultimately use a two-dimensional array dist[i][j] and continuously update it during the algorithm. Its meaning evolves to: at the current stage, the known shortest distance from vertex i to vertex j.

Detailed Algorithm Steps

Assume the graph has n vertices (numbered from 0 to n-1) and is represented by an n×n adjacency matrix graph. graph[i][j] represents the weight of the edge from vertex i to vertex j. If there is no direct edge between i and j, it is represented by infinity (∞).

Step 1: Initialization
Create a distance matrix dist of size n×n. Copy the graph's adjacency matrix directly into dist as the initial state.

  • For each vertex pair (i, j):
    • If i equals j, then the distance from a vertex to itself dist[i][j] = 0.
    • Otherwise, dist[i][j] = graph[i][j] (i.e., the edge weight, or ∞ if no direct edge exists).

This initial state dist[i][j] represents the shortest path from i to j when no intermediate vertices are allowed (i.e., taking the direct edge if it exists, or no path otherwise).

Step 2: Core Dynamic Programming Iteration
Now, we start gradually allowing each vertex as an intermediate vertex. We perform n loops, with k ranging from 0 to n-1. In each loop for k, we consider adding vertex k to the set of allowed intermediate vertices.

For each vertex pair (i, j), we ask the question: "Now that we are allowed to pass through vertex k, could the path from i to j become shorter by going through k?"

The specific update rule is as follows:
For all vertex pairs (i, j), check:
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

The meaning of this formula is:

  • dist[i][j]: The currently known shortest distance from i to j (when allowed to use the first k-1 vertices as intermediates).
  • dist[i][k]: The shortest distance from i to k, computed in a previous state using only the first k-1 intermediate vertices.
  • dist[k][j]: The shortest distance from k to j, similarly computed using only the first k-1 intermediate vertices.
  • dist[i][k] + dist[k][j]: This path represents going from i to k, then from k to j. This path is allowed to use vertex k as an intermediate.

We compare the "current shortest path without using k" with the "new path through k" and update dist[i][j] to the smaller value.

Important Detail: When calculating dist[i][k] and dist[k][j], since k is the intermediate vertex currently being considered, we use the values computed in the previous round (stage k-1). This ensures we do not create a path that passes through the same vertex k multiple times, adhering to the "non-aftereffect" property of dynamic programming.

Step 3: Completion of Iteration
After iterating k from 0 to n-1, the values in the matrix dist (i.e., dist[i][j]) represent the true shortest path distances from vertex i to vertex j. This is because we have now considered all n vertices in the graph as potential intermediate vertices.

Algorithm Demonstration (A Simple Example)

Consider a graph with 3 vertices (0, 1, 2), with the following adjacency matrix (∞ represents no direct edge):

Initial graph:
   0   1   2
0  0   3  ∞
1  ∞   0   1
2  2   ∞   0

  1. Initialize dist matrix: Direct copy of graph.

    k = -1 (Initial state, no intermediate vertices allowed)
dist:
    0   1   2
0   0   3   ∞
1   ∞   0   1
2   2   ∞   0

  2. First iteration (k=0): Allow vertex 0 as an intermediate.
    Check all (i, j) pairs:

    • (1,2): dist[1][2] = min(∞, dist[1][0] + dist[0][2]) = min(∞, ∞ + ∞) = ∞ -> unchanged.
    • (2,1): dist[2][1] = min(∞, dist[2][0] + dist[0][1]) = min(∞, 2 + 3) = 5 -> updated to 5!
      Updated dist matrix:
    k = 0 (Allowed intermediate vertex: 0)
dist:
    0   1   2
0   0   3   ∞
1   ∞   0   1
2   2   5   0

    Now we know that from 2 to 1, we can go via 0 with distance 5, which is shorter than the previous ∞ (no direct path).

  3. Second iteration (k=1): Allow vertices 0 and 1 as intermediates.
    Check all (i, j) pairs:

    • (0,2): dist[0][2] = min(∞, dist[0][1] + dist[1][2]) = min(∞, 3 + 1) = 4 -> updated to 4!
    • (2,0): dist[2][0] = min(2, dist[2][1] + dist[1][0]) = min(2, 5 + ∞) = 2 -> unchanged.
    • (2,2): dist[2][2] = min(0, dist[2][1] + dist[1][2]) = min(0, 5+1)=0 -> unchanged.
      Updated dist matrix:
    k = 1 (Allowed intermediate vertices: 0,1)
dist:
    0   1   2
0   0   3   4
1   ∞   0   1
2   2   5   0

    Now we know that from 0 to 2, we can go via 1 with distance 4.

  4. Third iteration (k=2): Allow all vertices (0,1,2) as intermediates.
    Check all (i, j) pairs:

    • (0,0): dist[0][0] = min(0, dist[0][2] + dist[2][0]) = min(0, 4+2)=0 -> unchanged.
    • (0,1): dist[0][1] = min(3, dist[0][2] + dist[2][1]) = min(3, 4+5)=3 -> unchanged.
    • (1,0): dist[1][0] = min(∞, dist[1][2] + dist[2][0]) = min(∞, 1+2)=3 -> updated to 3!
    • (1,1): dist[1][1] = min(0, dist[1][2] + dist[2][1]) = min(0, 1+5)=0 -> unchanged.
      Updated dist matrix (final result):
    k = 2 (Allowed all intermediate vertices)
dist:
    0   1   2
0   0   3   4
1   3   0   1
2   2   5   0

Finally, the dist matrix contains the shortest path distances between all pairs of vertices.

Time and Space Complexity

  • Time Complexity: O(n³). Because there are three nested loops iterating over k, i, j, each running n times.
  • Space Complexity: O(n²). Only need to store an n×n distance matrix.

Algorithm Characteristics and Considerations

  • Negative-weight edges: Floyd-Warshall can handle graphs with negative-weight edges.
  • Negative-weight cycles: The algorithm cannot handle graphs containing negative-weight cycles. A negative-weight cycle means one can traverse it infinitely, making path lengths approach negative infinity. This can be detected by checking the main diagonal of the final matrix: if any dist[i][i] < 0 exists, then there is a negative-weight cycle starting and ending at i.
  • Path reconstruction: If the specific shortest path (not just the distance) needs to be output, a next matrix can be maintained to record the successor of i on the shortest path from i to j. When dist[i][j] is updated because a shorter path is found, also update next[i][j] = next[i][k].