Floyd-Warshall Algorithm

Concept

Floyd-Warshall computes the shortest path between every pair of nodes in a weighted graph. It uses dynamic programming: for each intermediate node k, it checks if going through k gives a shorter path between every pair (i, j).

When to Use

  • ▸All-pairs shortest path (distance from every node to every other node)
  • ▸Small graphs (V <= 500) where you need all distances
  • ▸Transitive closure (checking reachability between all pairs)
  • ▸Problems that query shortest path between many different pairs

Intuition

Start with direct edge weights. Then ask: 'Can we do better by routing through node 0?' Update all pairs. Then ask: 'Can we do better by also routing through node 1?' And so on for every node. After considering all possible intermediate nodes, we have the shortest path for every pair. The triple nested loop is deceptively simple but powerful.

Complexity

Time
O(V^3)
Space
O(V^2)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    const int inf = 1e9+7;
    vector<vector<int>> adj(n, vector<int>(n, inf));

    for(int i = 0; i < n; i++) adj[i][i] = 0;

    int u, v, w;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        adj[u][v] = w;
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(adj[i][k] + adj[k][j] < adj[i][j]){
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(adj[i][j] == inf) cout << "inf ";
            else cout << adj[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

// Sample Input:
// 4 5
// 0 1 3
// 0 3 7
// 1 2 2
// 2 3 1
// 3 1 2
//
// Sample Output:
// 0 3 5 6
// inf 0 2 3
// inf 3 0 1
// inf 2 4 0