Floyd-Warshall Algorithm

The Floyd-Warshall algorithm solves the All-Pairs Shortest Path (APSP) problem: find the shortest distance between every pair of vertices in a weighted directed graph. It runs in \(O(V^3)\) time and handles negative edge weights (but not negative cycles).

Core Idea (Dynamic Programming):
Let \(\text{dist}[i][j][k]\) = shortest path from \(i\) to \(j\) using only vertices \(\{0, 1, \ldots, k\}\) as intermediates. We gradually add intermediates one by one.

Why Not Run Dijkstra \(V\) Times?

Algorithm	Time	Negative weights?	Best for
Floyd-Warshall	\(O(V^3)\)	Yes (no neg cycles)	Dense graphs, small V
Dijkstra × V	\(O(V \cdot (E + V\log V))\)	No	Sparse, non-negative
Bellman-Ford × V	\(O(V^2 E)\)	Yes	Negative weights, sparse
Johnson's	\(O(VE + V^2 \log V)\)	Yes	Sparse, large V

Mathematical Formulation

Initial: \(\text{dist}[i][j] = \text{weight}(i \to j)\) (or \(\infty\) if no edge; 0 if \(i=j\))

DP Recurrence (for each intermediate k):

\[\text{dist}[i][j] \leftarrow \min\!\left(\text{dist}[i][j],\; \text{dist}[i][k] + \text{dist}[k][j]\right)\]

Applied for all \(k = 0 \ldots V-1\), then all pairs \((i,j)\).

Negative Cycle Detection: If any \(\text{dist}[v][v] < 0\) after all iterations → negative cycle exists.

Graph Example & Initial Matrix

Step-by-Step: Matrix Updates

For each intermediate vertex \(k\), we check all pairs \((i,j)\): can path \(i \to k \to j\) improve \(\text{dist}[i][j]\)?

Click a step to begin...

Path Reconstruction Visualization

C++ Implementation

Complete Floyd-Warshall with Path Reconstruction

#include <iostream>
#include <vector>
#include <climits>
#include <string>
using namespace std;

const int INF = INT_MAX / 2;  // Use INT_MAX/2 to prevent overflow

struct Graph {
    int V;
    vector<vector<int>> dist;  // dist[i][j] = shortest dist i→j
    vector<vector<int>> next;  // next[i][j] = next vertex on shortest path

    Graph(int V) : V(V),
        dist(V, vector<int>(V, INF)),
        next(V, vector<int>(V, -1)) {
        for (int i = 0; i < V; i++) dist[i][i] = 0;
    }

    void addEdge(int u, int v, int w) {
        dist[u][v] = w;
        next[u][v] = v;  // direct edge: next step is v itself
    }

    // Run Floyd-Warshall. Returns false if negative cycle detected.
    bool floydWarshall() {
        for (int k = 0; k < V; k++) {           // try each intermediate
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] == INF || dist[k][j] == INF) continue;
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];  // route through k
                    }
                }
            }
        }
        // Negative cycle: any dist[v][v] < 0
        for (int v = 0; v < V; v++)
            if (dist[v][v] < 0) return false;
        return true;
    }

    // Reconstruct path from u to v
    vector<int> path(int u, int v) {
        if (next[u][v] == -1) return {};   // unreachable
        vector<int> p = {u};
        while (u != v) { u = next[u][v]; p.push_back(u); }
        return p;
    }

    void printMatrix() {
        cout << "dist[][] (INF shown as ∞):\n";
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF) cout << "  ∞";
                else cout << "  " << dist[i][j];
            }
            cout << "\n";
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0,1,3);
    g.addEdge(0,3,7);
    g.addEdge(1,2,5);
    g.addEdge(1,3,1);
    g.addEdge(2,0,2);
    g.addEdge(2,3,-3);
    g.addEdge(3,2,4);

    if (!g.floydWarshall()) {
        cout << "Negative cycle detected!\n";
        return 1;
    }

    g.printMatrix();

    // Print all pairs shortest paths
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (i == j || g.dist[i][j] == INF) continue;
            auto p = g.path(i, j);
            cout << i << " → " << j << " (dist=" << g.dist[i][j] << "): ";
            for (int v : p) cout << v << " ";
            cout << "\n";
        }
    }
    return 0;
}
                

Negative Cycle Detection in Practice

Detecting negative cycles: After all \(V\) iterations, check if dist[v][v] < 0 for any vertex \(v\). This means there is a path from \(v\) to itself with negative total weight — any shortest path passing through that cycle becomes \(-\infty\).

// Identify ALL vertices affected by a negative cycle
vector<bool> inNegCycle(int V, vector<vector<int>>& dist) {
    vector<bool> neg(V, false);
    for (int k = 0; k < V; k++) {
        if (dist[k][k] < 0) {           // k is on a negative cycle
            for (int i = 0; i < V; i++)
                for (int j = 0; j < V; j++)
                    if (dist[i][k] != INF && dist[k][j] != INF)
                        neg[i] = neg[j] = true;  // affected vertices
        }
    }
    return neg;
}
                

Real-World Applications

Domain	Application	Why Floyd-Warshall?
Network Routing	BGP/OSPF routing tables — compute all-pairs reachability	Dense AS graphs, need all pairs
Currency Arbitrage	Detect negative cycles in currency exchange rate graph (log weights)	Negative cycle = arbitrage opportunity
Social Networks	Compute betweenness centrality — how many shortest paths pass through a node	All-pairs paths needed
Game Maps	Precompute distance between all city pairs in strategy games	Small maps, real-time queries
Transitive Closure	Can vertex \(i\) reach vertex \(j\)? (set all weights to 1)	Boolean variant in \(O(V^3)\)
GIS / Maps	Distance matrix for travelling salesman approximations	Pre-compute distance table

Currency Arbitrage Example

Build a graph where edge weight \((i,j)\) = \(-\log(\text{rate}_{ij})\). A negative cycle in this graph means there exists a sequence of currency conversions with a net gain. Floyd-Warshall detects such negative cycles in \(O(V^3)\).

Complexity Summary

Time: \(O(V^3)\) — three nested loops over \(V\) vertices

Space: \(O(V^2)\) — the distance matrix

Limitation: Only practical for \(V \leq 1000\) (beyond that, \(V^3 = 10^9\) operations)