Floyd-Warshall Algorithm

in Computer Science on Algorithms · 9 min

Introduction

The Floyd–Warshall algorithm is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with positive and negative-edge weights but does not work with graphs containing negative cycles. The algorithm is particularly useful for dense graphs and is often used in network routing protocols.

Explanation

The Floyd–Warshall algorithm works by iteratively improving the shortest path estimates between all pairs of vertices.

  1. Create a distance matrix dist where dist[i][j] is the weight of the edge from vertex i to vertex j. If there is no edge, set it to infinity. Set dist[i][i] = 0 for all vertices i.
  2. For each vertex k, iterate through all pairs of vertices (i, j) and update the distance matrix: \[ \text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) \]

The interactive demo below uses the same recurrence. At step $k$, the matrix allows paths whose internal vertices are contained in the first $k$ vertices of the order

\[ A,B,C,D. \]

Step
Allowed intermediate vertices:
Changed cells:
Current intermediate vertex $k$
Distance improved in this iteration

For example, when $k=C$, the entry from $B$ to $D$ improves because

\[ \mathrm{dist}[B][C]+\mathrm{dist}[C][D] = -3+4=1. \]

Proof of Correctness

Order the vertices as

\[ 1,2,\ldots,V. \]

Let $D_k[i][j]$ be the minimum weight of a path from $i$ to $j$ whose internal vertices are contained in

\[ \Set{1,2,\ldots,k}. \]

The Floyd–Warshall invariant is that after finishing the iteration for $k$, the matrix entry dist[i][j] is exactly $D_k[i][j]$.

Proof. For $k=0$, no internal vertex is allowed. Thus the best path from $i$ to $j$ is either the direct edge $i\to j$, the empty path when $i=j$, or no path. This is exactly the initialization of the distance matrix.

Assume the invariant holds after iteration $k-1$. Consider a shortest path counted by $D_k[i][j]$. Either it does not use vertex $k$ as an internal vertex, in which case its weight is $D_{k-1}[i][j]$, or it uses $k$. In the second case, split the path at $k$. The subpath from $i$ to $k$ and the subpath from $k$ to $j$ have internal vertices only in

\[ \Set{1,2,\ldots,k-1}. \]

Hence the best such path has weight

\[ D_{k-1}[i][k]+D_{k-1}[k][j]. \]

Therefore

\[ D_k[i][j] =\min\left(D_{k-1}[i][j],D_{k-1}[i][k]+D_{k-1}[k][j]\right). \]

This is exactly the update performed by the algorithm. By induction, after $k=V$ all vertices are allowed as internal vertices, so every shortest path is considered.

If a negative cycle is reachable from $i$ and can reach $j$, the shortest distance from $i$ to $j$ is not well-defined as a finite value. This is why the usual shortest-path interpretation assumes no negative cycles.

Complexity

The time complexity of the Floyd–Warshall algorithm is $O(V^3)$, where $V$ is the number of vertices in the graph. This is because the algorithm consists of three nested loops, each iterating over all vertices. The space complexity is $O(V^2)$ due to the distance matrix.

Code

Let’s see the sample code.

const int MAX;
const int INF;
int dist[MAX][MAX];
int N; // Number of vertices

void init(){
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)
        dist[i][j] = (i==j)?0:INF;
}

void FloydWarshall(){
    for(int k=1; k<=N; k++)
        for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}

Applications

The Floyd–Warshall algorithm is widely used in various applications, including:

  • Optimizing network routing protocols.
  • Finding the transitive closure of a directed graph.
  • Inverting real-valued matrices. (Gauss–Jordan elimination)