Skip to content

Floyd–Warshall (All-Pairs Shortest Paths)

Floyd–Warshall computes shortest paths between every pair of vertices in \(O(|V|^3)\). It allows negative edges (but not negative cycles reachable from a node—detect those during run or with a check).

Idea

dist[i][j] = shortest distance from i to j using only intermediate vertices from {0..k-1}; relax by trying vertex k as last hop.

Implementation

Initialize dist[i][j] with edge weights, 0 on diagonal, INF if no edge.

#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

// After: dist[i][j] = shortest i -> j (or INF if unreachable)
void floydWarshall(vector<vector<int>>& dist) {
    int n = (int)dist.size();
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

bool hasNegativeCycle(const vector<vector<int>>& dist) {
    int n = (int)dist.size();
    for (int i = 0; i < n; i++)
        if (dist[i][i] < 0) return true;
    return false;
}

When to use

  • Dense graphs, \(|V| \le 500\)–\(1000\) typical.
  • All-pairs distances needed (e.g. DP over pairs of cities).
  • For single-source non-negative weights, Dijkstra is usually faster.