All-Pairs Shortest Paths (Floyd-Warshall)

The Floyd-Warshall algorithm computes the shortest paths between every pair of vertices in a weighted graph. Unlike Dijkstra or Bellman-Ford, which are single-source algorithms, Floyd-Warshall solves the all-pairs shortest path problem in one run.

It is especially useful for dense graphs and for scenarios where distances between all pairs of nodes are required.

When to Use Floyd-Warshall

Floyd-Warshall is appropriate when:

• You need shortest paths between all pairs of vertices
• The graph is small to medium sized
• Edge weights may be negative (but no negative cycles)
• Simplicity is preferred over performance

Key Idea

The algorithm is based on dynamic programming.

For every pair of vertices (i, j), it checks whether going through an intermediate vertex k produces a shorter path:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

By considering each vertex as an intermediate, all shortest paths are discovered.

Algorithm Steps

1. Initialize a distance matrix from the graph

2. Set distance from a vertex to itself as 0

3. For each intermediate vertex k:

   • Update all (i, j) pairs

4. Final matrix contains all shortest paths

Example Graph

      3
A --------> B
| \         |
8  \5       |2
|   \       |
v    v      v
C --------> D
      1

Graph Representation

Floyd-Warshall uses an adjacency matrix, where:

• dist[i][j] stores the shortest distance from i to j
• ∞ represents no direct edge

Rust Implementation

const INF: i32 = i32::MAX / 2;

pub fn floyd_warshall(mut dist: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = dist.len();

    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                let through_k = dist[i][k] + dist[k][j];
                if through_k < dist[i][j] {
                    dist[i][j] = through_k;
                }
            }
        }
    }

    dist
}

Example Usage

fn main() {
    let graph = vec![
        vec![0,   3,   INF, 5],
        vec![INF, 0,   2,   INF],
        vec![8,   INF, 0,   1],
        vec![INF, INF, INF, 0],
    ];

    let shortest = floyd_warshall(graph);

    for row in shortest {
        println!("{:?}", row);
    }
}

Output:

[0, 3, 5, 4]
[10, 0, 2, 3]
[8, 11, 0, 1]
[18, 21, 23, 0]

Negative Cycle Detection

After running the algorithm:

• If dist[i][i] < 0 for any vertex i
• A negative-weight cycle exists

This makes Floyd-Warshall useful for graph validation.

Time and Space Complexity

Time Complexity

Space Complexity

Floyd-Warshall vs Other Shortest Path Algorithms

Limitations

• Not suitable for large graphs
• High memory usage
• Slower than single-source algorithms

Summary

• Floyd-Warshall computes shortest paths between all vertex pairs
• Uses dynamic programming
• Supports negative weights (no negative cycles)
• Best for dense or small graphs

Playground Links

Rust - Floyd-Warshall