Floyd-Warshall Algorithm: All-Pairs Shortest Paths

The Floyd-Warshall algorithm computes the shortest path between every pair of vertices at once. It’s a beautifully short dynamic-programming routine: three nested loops over a V × V distance matrix, asking for each pair (i, j) whether routing through an intermediate vertex k is shorter. It runs in O(V³) time and O(V²) space and tolerates negative weights (but not negative cycles).

The key idea

Let dist[i][j] be the shortest known distance from i to j. Consider intermediate vertices 0, 1, …, V-1 one at a time. When you “allow” vertex k, every pair gets the chance to improve:

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

The crucial detail is loop order: k must be the outermost loop so that dist[i][k] and dist[k][j] already account for all smaller intermediates.

const long long INF = 1e18;

// dist starts as the adjacency matrix (INF where no edge, 0 on diagonal)
void floydWarshall(std::vector<std::vector<long long>>& dist) {
    int n = dist.size();
    for (int k = 0; k < n; k++)                    // intermediate (outermost!)
        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][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

static final long INF = (long) 1e18;

// dist starts as the adjacency matrix (INF where no edge, 0 on diagonal)
void floydWarshall(long[][] dist) {
    int n = dist.length;
    for (int k = 0; k < n; k++)                    // intermediate (outermost!)
        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][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

const INF = Infinity;

// dist starts as the adjacency matrix (INF where no edge, 0 on diagonal)
function floydWarshall(dist) {
  const n = dist.length;
  for (let k = 0; k < n; k++)                      // intermediate (outermost!)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];
}

INF = float('inf')

# dist starts as the adjacency matrix (INF where no edge, 0 on diagonal)
def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):                              # intermediate (outermost!)
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

Pitfall: Putting k anywhere but the outermost loop gives wrong answers — it’s the single most common Floyd-Warshall bug. Also initialize the diagonal dist[i][i] = 0 and use a finite-but-huge INF you guard against (as in C++/Java) so INF + weight doesn’t overflow.

Detecting negative cycles

After the algorithm, if any diagonal entry dist[i][i] < 0, vertex i lies on a negative cycle (it can reach itself at negative cost). This is the all-pairs analogue of the negative-cycle test in Bellman-Ford.

Reconstructing paths

Keep a next[i][j] matrix: initialize next[i][j] = j for each direct edge, and whenever you improve dist[i][j] through k, set next[i][j] = next[i][k]. To rebuild a path, follow next from i toward j.

Complexity and trade-offs

• Time: O(V³) — three nested loops.
• Space: O(V²) for the matrix.

Approach              All-pairs cost        Negative weights
Floyd-Warshall        O(V^3)                yes (no neg cycles)
Dijkstra x V sources  O(V*(V+E) log V)      no
Bellman-Ford x V      O(V^2 * E)            yes

When to use it

Floyd-Warshall wins when you need every pair’s distance on a small, dense graph (think V up to a few hundred), or for transitive closure (replace min/+ with OR/AND to answer “can i reach j?”). For a single source on a large sparse graph, run Dijkstra or Bellman-Ford instead.