Floyd–Warshall

Use Floyd–Warshall when shortest distances are needed between many or all vertex pairs and V is small enough for cubic time and quadratic memory.

The DP state

Before processing intermediate vertex k, distance[i][j] is the shortest known path from i to j whose internal vertices come only from 0 .. k - 1.

When k becomes available, every best path either:

• skips k, keeping distance[i][j]; or
• uses k, combining distance[i][k] + distance[k][j].

That gives the recurrence:

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

flowchart LR
  accTitle: Floyd-Warshall considers whether a shortest path uses k
  accDescr: At stage k, the best path from i to j is the smaller of the previous path that skips k and the two-part route from i to k to j.
  A["Previous best i to j<br/>skip k"] --> M{"Take the smaller cost"}
  B["Best i to k"] --> C["Add the two route pieces"]
  D["Best k to j"] --> C
  C -->|"use k"| M
  M --> E["New best i to j<br/>internal vertices through k allowed"]

This is staged DP on the allowed intermediate set: k must be the outer loop because it defines which subproblem answers are legal to combine.

Annotated blueprint

distance[i][i] = 0
distance[u][v] = min(existing, edge_weight)        # keep best parallel edge

for k in vertices:                                 # newly allowed intermediate
    for i in vertices:
        if distance[i][k] is infinity: continue
        for j in vertices:
            if distance[k][j] is infinity: continue
            distance[i][j] = min(
                distance[i][j],
                distance[i][k] + distance[k][j]    # route through k
            )

After all iterations, distance[v][v] < 0 proves that v lies on or can participate in a negative cycle under the represented reachability.

When to choose it

• V is a few hundred or less, depending on language and limits.
• The graph is dense.
• Many pair queries justify preprocessing.
• Edge weights may be negative, but shortest paths are meaningful only without relevant negative cycles.

For sparse graphs with nonnegative weights, repeated Dijkstra may be more appropriate.

Complexity and traps

• Time: O(V³).
• Space: O(V²).
• Initialize the diagonal to zero.
• Take the minimum over parallel edges.
• Guard infinity before addition and consider overflow.
• Put k in the outer loop; it represents the DP stage.

Reference

• Princeton: Floyd–Warshall API
• Princeton: shortest-path chapter

Tested template

PythonC++17C++11

def floyd_warshall(matrix: Sequence[Sequence[float | int]]) -> list[list[float | int]]:
    """Return all-pairs shortest distances from an adjacency matrix."""
    size = len(matrix)
    if any(len(row) != size for row in matrix):
        raise ValueError("distance matrix must be square")
    distance = [list(row) for row in matrix]
    for vertex in range(size):
        distance[vertex][vertex] = min(distance[vertex][vertex], 0)

    for middle in range(size):
        for left in range(size):
            if distance[left][middle] == inf:
                continue
            for right in range(size):
                if distance[middle][right] == inf:
                    continue
                through_middle = distance[left][middle] + distance[middle][right]
                if through_middle < distance[left][right]:
                    # After phase middle, only vertices 0..middle may be internal.
                    distance[left][right] = through_middle

    if any(distance[vertex][vertex] < 0 for vertex in range(size)):
        raise ValueError("graph contains a negative cycle")
    return distance

inline std::vector<std::vector<long long>> floyd_warshall(
    std::vector<std::vector<long long>> distance) {
  const int size = static_cast<int>(distance.size());
  const long long infinity = std::numeric_limits<long long>::max();
  for (const auto& row : distance) {
    if (static_cast<int>(row.size()) != size) {
      throw std::invalid_argument("distance matrix must be square");
    }
  }
  for (int vertex = 0; vertex < size; ++vertex) {
    distance[vertex][vertex] = std::min(0LL, distance[vertex][vertex]);
  }
  for (int middle = 0; middle < size; ++middle) {
    for (int left = 0; left < size; ++left) {
      if (distance[left][middle] == infinity) {
        continue;
      }
      for (int right = 0; right < size; ++right) {
        if (distance[middle][right] == infinity) {
          continue;
        }
        const long long suffix = distance[middle][right];
        if ((suffix > 0 && distance[left][middle] > infinity - suffix) ||
            (suffix < 0 && distance[left][middle] <
                               std::numeric_limits<long long>::min() - suffix)) {
          throw std::overflow_error("Floyd-Warshall distance overflow");
        }
        const long long candidate =
            distance[left][middle] + distance[middle][right];
        if (candidate < distance[left][right]) {
          // Phase middle permits vertices 0..middle as internal vertices.
          distance[left][right] = candidate;
        }
      }
    }
  }
  for (int vertex = 0; vertex < size; ++vertex) {
    if (distance[vertex][vertex] < 0) {
      throw std::invalid_argument("graph contains a negative cycle");
    }
  }
  return distance;
}

inline std::vector<std::vector<long long>> floyd_warshall(
    std::vector<std::vector<long long>> distance) {
  const int size = static_cast<int>(distance.size());
  const long long infinity = std::numeric_limits<long long>::max();
  for (const auto& row : distance) {
    if (static_cast<int>(row.size()) != size) {
      throw std::invalid_argument("distance matrix must be square");
    }
  }
  for (int vertex = 0; vertex < size; ++vertex) {
    distance[vertex][vertex] = std::min(0LL, distance[vertex][vertex]);
  }
  for (int middle = 0; middle < size; ++middle) {
    for (int left = 0; left < size; ++left) {
      if (distance[left][middle] == infinity) {
        continue;
      }
      for (int right = 0; right < size; ++right) {
        if (distance[middle][right] == infinity) {
          continue;
        }
        const long long suffix = distance[middle][right];
        if ((suffix > 0 && distance[left][middle] > infinity - suffix) ||
            (suffix < 0 && distance[left][middle] <
                               std::numeric_limits<long long>::min() - suffix)) {
          throw std::overflow_error("Floyd-Warshall distance overflow");
        }
        const long long candidate =
            distance[left][middle] + distance[middle][right];
        if (candidate < distance[left][right]) {
          // Phase middle permits vertices 0..middle as internal vertices.
          distance[left][right] = candidate;
        }
      }
    }
  }
  for (int vertex = 0; vertex < size; ++vertex) {
    if (distance[vertex][vertex] < 0) {
      throw std::invalid_argument("graph contains a negative cycle");
    }
  }
  return distance;
}

The tested template accepts an infinity sentinel, guards unreachable additions, normalizes the diagonal, and rejects a negative diagonal after all phases.