The challenge
Compute shortest distances between every ordered pair of vertices. Identify whether the graph contains any negative cycle.
Directed graph; negative edges are allowed. Affected pairs have no finite minimum when they can pass through a negative cycle.
Example
On the negative-edge example, A → E improves from ∞ to 5. E → A stays ∞ because no directed return path exists.
Use the walkthrough below to inspect the input and each state change.
See Floyd–Warshall, step by step
Follow the edges. Watch the state change.
| From / to | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 4 | ∞ | ∞ | ∞ | 1 |
| B | ∞ | 0 | -2 | ∞ | ∞ | ∞ |
| C | ∞ | ∞ | 0 | 3 | ∞ | ∞ |
| D | ∞ | ∞ | ∞ | 0 | 1 | ∞ |
| E | ∞ | ∞ | ∞ | ∞ | 0 | ∞ |
| F | ∞ | 2 | ∞ | ∞ | 8 | 0 |
Initialize direct distances.
The diagonal is zero, direct edges keep their minimum weight, and all other pairs start at infinity. Rows are sources; columns are destinations.
distance[i][i] = 0; distance[u][v] = weightView input edges
A → B (4) · A → F (1) · F → B (2) · B → C (-2) · F → E (8) · C → D (3) · D → E (1)
Put it into code
After iteration k, routes may use only the first k + 1 vertices as intermediates.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
from math import inf
def floyd_warshall(n, edges):
# Directed edges: (u, v, weight).
distance = [[inf] * n for _ in range(n)]
for u in range(n):
distance[u][u] = 0
for u, v, weight in edges:
distance[u][v] = min(distance[u][v], weight)
for k in range(n): # Intermediate vertex MUST be outermost.
for i in range(n):
for j in range(n):
if distance[i][k] != inf and distance[k][j] != inf:
distance[i][j] = min(
distance[i][j], distance[i][k] + distance[k][j])
negative_cycle = any(distance[u][u] < 0 for u in range(n))
return distance, negative_cycle # Affected pairs have no finite minimum.#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
using ll = long long;
constexpr ll INF = (1LL << 60);
std::pair<std::vector<std::vector<ll>>, bool> floyd_warshall(
int n, const std::vector<std::tuple<int, int, ll>>& edges) {
// All intermediate sums must fit in long long.
std::vector<std::vector<ll>> d(n, std::vector<ll>(n, INF));
for (int u = 0; u < n; ++u) d[u][u] = 0;
for (auto [u, v, weight] : edges)
d[u][v] = std::min(d[u][v], weight);
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (d[i][k] != INF && d[k][j] != INF)
d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
bool negative_cycle = false;
for (int u = 0; u < n; ++u)
if (d[u][u] < 0) negative_cycle = true;
return {d, negative_cycle};
}