Floyd-Warshall Algorithm

On this page

Interactive

All-pairs shortest paths, one intermediate vertex at a time

Step kAutoReset

Directed graph

Distance matrix

	A	B	C	D	E
A	0	∞	∞	∞	∞
B	∞	0	∞	∞	∞
C	∞	∞	0	∞	∞
D	∞	∞	∞	0	∞
E	∞	∞	∞	∞	0

Press Step k to allow A as an intermediate vertex.

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

Floyd–Warshall for all-pairs shortest paths

When distances are needed between many pairs of vertices, repeating a single-source search may be wasteful. Floyd–Warshall uses dynamic programming to consider every vertex as a possible intermediate point. It handles negative edge weights, as long as a negative cycle does not lie on a route relevant to the pair being queried.

The recurrence and its invariant

Number the vertices 0 through V - 1. After processing intermediate vertices 0, ..., k - 1, let D[i][j] be the lightest path from i to j whose internal vertices are among those processed. Initially, no intermediate vertices are allowed: set D[i][i] = 0, each direct edge to its weight (taking the minimum for parallel edges), and absent edges to infinity.

At stage k, a best path either avoids k or uses it. In the latter case, split at k; both subpaths use only earlier intermediate vertices. Therefore the update is

$$D[i][j]\leftarrow\min(D[i][j],D[i][k]+D[k][j]).$$

1. Before stage k Allowed internal vertices: {0, …, k − 1}

   D[i][j] uses only these processed vertices.

2. Update using k D[i][j] ← min(D[i][j], D[i][k] + D[k][j])

   A shortest path either avoids k or splits at k.

3. After stage k Allowed internal vertices: {0, …, k}

   Finish this stage before k + 1 is allowed.

The intermediate-vertex loop must be outermost: the whole k stage must be complete before allowing k+1. This invariant is what makes the in-place table implement the recurrence.

Runnable C++ example

The function below assumes n >= 0, every edge endpoint is in [0,n), and input weights and every finite sum formed by the recurrence stay strictly between -INF and INF and within int64_t range. INF marks unreachable pairs; guard both addends before adding it. Zero-weight edges are valid, so edge presence is not tested by truthiness. The example reads a directed graph and prints INF for unreachable pairs. The structured bindings require C++17 or later.

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <tuple>
#include <vector>

using Weight = std::int64_t;
constexpr Weight INF = (Weight{1} << 60);

std::vector<std::vector<Weight>> floydWarshall(
    int n, const std::vector<std::tuple<int, int, Weight>>& edges) {
  std::vector<std::vector<Weight>> dist(n, std::vector<Weight>(n, INF));
  for (int i = 0; i < n; ++i) dist[i][i] = 0;
  for (const auto& [from, to, weight] : edges)
    dist[from][to] = std::min(dist[from][to], weight);

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i) {
      if (dist[i][k] == INF) continue;
      for (int j = 0; j < n; ++j) {
        if (dist[k][j] == INF) continue;
        dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  return dist;
}

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::tuple<int, int, Weight>> edges;
  for (int e = 0; e < m; ++e) {
    int from, to;
    Weight weight;
    std::cin >> from >> to >> weight;
    edges.emplace_back(from, to, weight);
  }
  const auto dist = floydWarshall(n, edges);
  for (const auto& row : dist) {
    for (int j = 0; j < n; ++j) {
      if (j) std::cout << ' ';
      if (row[j] == INF) std::cout << "INF";
      else std::cout << row[j];
    }
    std::cout << '\n';
  }
}

Example input:

4 5
0 1 4
0 2 11
1 2 -2
2 3 3
1 3 7

Output:

0 4 2 5
INF 0 -2 1
INF INF 0 3
INF INF INF 0

For 0 to 3, the best route is 0→1→2→3, with cost 4-2+3=5. The negative edge is fine; this graph has no negative cycle.

Cost and negative cycles

The three nested loops take O(V^3) time; the distance table takes O(V^2) space. This is useful when many or all pairs are needed, but a single-source method may be preferable when only one source matters.

A negative cycle can be repeated to make a walk arbitrarily cheap. After the updates, dist[v][v] < 0 signals a negative cycle. A pair (i,j) has no finite shortest distance if some such v is reachable from i and can reach j; otherwise a negative cycle elsewhere does not invalidate that pair. Floyd–Warshall can still compute finite distances for unaffected pairs, but affected entries must not be reported as finite shortest paths.

Takeaway: process intermediate vertices in the outer loop, skip unreachable halves before addition, and interpret negative cycles pair by pair.