Floyd-Warshall all-pairs shortest paths

Why this matters

Dijkstra's algorithm and BFS start from one vertex and find the cost to every other vertex. If you need the cost between every pair of vertices, you could run Dijkstra once from each vertex. That works, but it is more code to keep correct, and it does not handle negative edge weights. The Floyd-Warshall algorithm does all pairs in one short piece of code, and it handles negative weights as long as there is no negative loop.

It is a good fit when the graph has a few hundred vertices or fewer. A routing table for a small network, the distance between every pair of cities in a list of 50, or a check of which tasks can reach which others are typical examples. The Bellman-Ford lesson earlier in this module covered one start vertex with negative weights. This lesson covers every start at once.

You need two-dimensional vectors and the min function from the STL. You also need the idea of a negative edge, which the Bellman-Ford lesson introduced.

One table of costs

Imagine four towns, A, B, C and D, with one-way roads between them. A one-way road can only be used in the direction it points. Each road has a cost.

The goal is a table with one row for each starting town and one column for each destination. The cell in row i and column j holds the cheapest cost from town i to town j. That table is called the distance matrix. It is an n by n grid, where n is the number of vertices.

Before the algorithm runs, the table has three kinds of values:

• The diagonal (row i, column i) is 0. Getting from a town to itself costs nothing.
• A cell with a direct road holds that road's cost.
• Every other cell holds INF, a large number that means "no known path yet".

The word INF is a constant in the code. It is not a special C++ keyword. Choosing it needs care, and the mistakes section shows why.

The idea: allow one more stop at a time

The Floyd-Warshall algorithm does not search in the usual way. It asks a question that grows one step at a time: what is the cheapest path from i to j that is allowed to pass through only the vertices 0, 1, ..., k?

Start with k equal to 0. Only vertex 0 may be used as a stop on the way. For each pair (i, j), check whether going from i to 0 and then from 0 to j is cheaper than the current cell. If it is, update the cell.

Then move to k equal to 1. Now vertices 0 and 1 may both be used. A path might go through 0, then through 1, and the cell for that pair is updated again if the new total is cheaper. Continue for every vertex. When k reaches the last vertex, every path that uses any stops has been considered.

The reason this works is simple. Any shortest path visits some set of stops in some order. If you add the stops one number at a time, the shortest path using the first k stops is always found by the step for k. The table after the last step is complete.

The triple loop

Three nested loops do the whole job. The outer loop is the stop k. The two inner loops are the start i and the end j.

Here is the function. It takes the number of vertices and a list of edges. Each edge is three numbers: from, to, and cost:

#include <algorithm>
#include <array>
#include <limits>
#include <vector>
 
using namespace std;
 
constexpr long long INF = numeric_limits<long long>::max() / 4;
 
using Matrix = vector<vector<long long>>;
 
// Edges are (from, to, weight). Vertices are 0..n-1.
Matrix floydWarshall(int n, const vector<array<long long, 3>>& edges) {
    Matrix dist(n, vector<long long>(n, INF));
    for (int v = 0; v < n; ++v) dist[v][v] = 0;
    for (auto [a, b, w] : edges) {
        dist[a][b] = min(dist[a][b], w);
    }
 
    for (int k = 0; k < n; ++k) {          // intermediate vertex
        for (int i = 0; i < n; ++i) {      // start
            for (int j = 0; j < n; ++j) {  // end
                if (dist[i][k] == INF || dist[k][j] == INF) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    return dist;
}

Look at the last line of the inner loop. It is the whole idea. The cost of going from i to j through k is the cost from i to k plus the cost from k to j. If that is less than the current value, it is the new value.

The continue line skips the update when either half is unknown. Without it, INF plus a number would be treated as a real cost, and the table would fill with nonsense. The mistakes section shows what happens when the check is missing.

The min in dist[a][b] = min(dist[a][b], w); handles a graph with two roads between the same pair of towns. Only the cheaper one counts.

The table is printed with this helper. It writes INF for unknown cells and right-aligns each value in five characters:

#include <iomanip>
#include <iostream>
#include <string>
 
void printMatrix(const Matrix& d, const vector<string>& names) {
    cout << "     ";
    for (const string& s : names) cout << setw(5) << s;
    cout << "\n";
    for (size_t i = 0; i < d.size(); ++i) {
        cout << setw(5) << names[i];
        for (long long x : d[i]) {
            if (x >= INF) cout << setw(5) << "INF";
            else cout << setw(5) << x;
        }
        cout << "\n";
    }
}

Worked example 1: one-way towns

The first example uses four towns with positive costs only. The roads are:

• A to B costs 3
• B to C costs 4
• A to C costs 9
• C to D costs 2
• D to A costs 1

Here is the program's output:

     A    B    C    D
    A    0    3    7    9
    B    7    0    4    6
    C    3    6    0    2
    D    1    4    8    0
negative cycle: no

Check one cell by hand. The cheapest way from A to C is the route A -> B -> C, which costs 3 + 4 = 7. The direct road costs 9, so 7 wins, and the table shows 7. The cheapest way from A to D is A -> B -> C -> D, which costs 3 + 4 + 2 = 9, and the table shows 9.

The step with k equal to 0 already helps. Town D can reach A for 1, and A can reach B for 3. So the cost from D to B is 1 + 3 = 4. That update happens at the first step, because A is vertex 0.

Worked example 2: a negative road

Negative numbers are allowed here, as long as the graph has no loop with a negative total. Take three towns A, B and C, with these roads:

• A to B costs 4
• A to C costs 5
• C to B costs -3

The direct road from A to B costs 4. The road through C costs 5 + (-3) = 2. The second route is cheaper, and the table should show 2:

     A    B    C
    A    0    2    5
    B  INF    0  INF
    C  INF   -3    0

The value 2 in row A, column B is the cheaper route through C. Town B has no outgoing roads, so its row is INF everywhere except the diagonal. Town C reaches B for -3, which is the negative road.

Negative cycles

A negative cycle is a loop of roads whose costs add up to less than zero. Going round it once makes the total smaller, and going round it again makes it smaller still. If a loop like this can be reached, the shortest cost is not a fixed number. It keeps falling forever, so there is no shortest path.

Floyd-Warshall can find these loops with one check. The value dist[v][v] is the cost of a route from v back to v. Normally that is 0, because the empty route costs nothing. If a route that starts and ends at v has a negative cost, the diagonal cell becomes negative. So after the algorithm runs, any vertex with a negative diagonal value lies on a negative cycle.

Here is an example with a loop between B and C. The roads are A to B costs 2, B to C costs -1, C to B costs -1, and C to D costs 4. The loop B -> C -> B costs -1 + -1 = -2, which is negative:

     A    B    C    D
    A    0    0   -1    3
    B  INF   -2   -3    1
    C  INF   -3   -4    0
    D  INF  INF  INF    0
diagonal: A=0 B=-2 C=-4 D=0
vertices on a negative cycle: B C

The diagonal shows B and C negative, and A and D at 0. The code that prints the list of vertices on a negative cycle is one loop:

bool negative = false;
for (int v = 0; v < n; ++v) {
    if (dist[v][v] < 0) {
        cout << "vertex " << v << " is on a negative cycle\n";
        negative = true;
    }
}

Some cells in this table are not real costs. The cell from A to C shows -1, but a route from A to C can go round the loop as many times as you like, so its true cost is unbounded. Once a negative cycle is on a route, every cell for a pair that can reach the cycle and then reach the destination is unreliable. The check on the diagonal tells you a problem exists. It does not tell you which other cells are wrong. In practice, when the diagonal check fails, treat the whole table as invalid.

Numbers can overflow

A negative cycle makes the numbers in the table grow more and more negative. Each step can add two very negative values together, which gives an even more negative one. For a small graph this is harmless. For a bigger graph it can exceed the limit of a 64-bit integer.

This program builds a path of 12 vertices with a -1 road in each direction between neighbours. Those roads form many negative cycles:

n = 12, smallest value in the matrix: -5592404
d[0][0] = -1864142, d[5][5] = -1865048

The values are already in the millions. The same program with 40 vertices printed this:

n = 40, smallest value in the matrix: -9223372036854775808
d[0][0] = -8198552921648696914, d[5][5] = -8198552921648697820

The smallest value printed is exactly the smallest possible long long. That means the values wrapped around past the limit. In C++ a signed integer that goes past its limit is undefined behaviour, which means the language does not say what happens. The printed numbers are one run of one compiler, not something you can rely on. The next section shows how to stop before the values get that large.

Stopping early

The negative cycle check does not have to wait for the last step. After each value of k, any negative diagonal value already proves a negative cycle exists. A diagonal value is the cost of a real route from a vertex back to itself, and a route that is negative means the cycle exists. So the program can stop at that point and report the problem.

Here is a version that does this. It returns false as soon as it sees a negative diagonal:

// Returns false as soon as a negative diagonal value shows up.
bool floydWarshallChecked(int n, const vector<array<long long, 3>>& edges, Matrix& dist) {
    dist.assign(n, vector<long long>(n, INF));
    for (int v = 0; v < n; ++v) dist[v][v] = 0;
    for (auto [a, b, w] : edges) dist[a][b] = min(dist[a][b], w);
    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) continue;
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        for (int v = 0; v < n; ++v) if (dist[v][v] < 0) return false;
    }
    return true;
}

The same chains, now with 12, 40 and 60 vertices, stop after the first step:

n=12 no negative cycle: no, d[0][0]=0
n=40 no negative cycle: no, d[0][0]=0
n=60 no negative cycle: no, d[0][0]=0

The value 0 for d[0][0] is the value at the moment the function returned, which is the first step. The matrix is not complete, and the function's answer is "no", so the caller must not use the table. The values stay small because the loop never ran the later steps.

Common mistakes

The mistakes below come from real runs of the code. Each one gives output that looks plausible, and only a check against a hand calculation reveals it.

Putting the stop loop in the wrong place

The variable k must be the outer loop. Putting i or j outside it gives wrong answers. Take four towns with roads 1 -> 3 costing 2, 3 -> 2 costing 8, and 2 -> 0 costing 8. The cheapest route from 1 to 0 is 1 -> 3 -> 2 -> 0, which costs 2 + 8 + 8 = 18. Running the same loops with i outside, as i, j, k, gives this:

correct k-outer: 1 to 0 = 18
wrong i-j-k:     1 to 0 = 2305843009213693951

The wrong version prints the INF value, so it says there is no route at all. The route exists. With i and j outside, the pair 1 to 0 is finished before the pair 1 to 2 has its route through 3, so the value needed at stop 2 is still INF. The rule to remember is that k is the outermost loop, and its meaning is "add one more allowed stop".

Using the largest number as INF

It is tempting to write INF as numeric_limits<long long>::max(), the biggest value the type can hold. The problem appears when you add two of them. The sum is too large for the type and wraps to a negative number. The continue line in the code above avoids adding two INF values. Without that line and with the largest value, the graph from worked example 1 printed:

max as INF, no skip: A to D = -9223372036854775805, B to A = 1

The value for A to D is negative and huge, which is wrong, because the correct answer is 9. The code uses numeric_limits<long long>::max() / 4. Two values of that size add up without overflowing, and the result still counts as "very large".

Starting the diagonal at INF

Every vertex can reach itself at cost 0. If the diagonal starts at INF, a vertex appears to have no route to itself, and the negative cycle check can no longer be trusted. The line for (int v = 0; v < n; ++v) dist[v][v] = 0; before the edge loop prevents this. Keep it before any edges are read.

Swapping the two ends of an edge

An edge is written as (from, to, weight). If you store it as dist[b][a], the table answers the question for the road in the other direction. For a directed graph this gives costs that look reasonable but belong to a different graph. The table's row is the start and the column is the end, so dist[a][b] is the road from a to b.

Using it on a large graph

The triple loop runs n times n times n steps. With 100 vertices that is one million steps, which is instant. With 2,000 vertices it is eight billion steps, and the matrix itself holds four million cells. For a sparse graph with many vertices, running Dijkstra from each vertex is usually faster. Floyd-Warshall is simplest when the table fits in memory and the graph is small or dense.

Practice

Each exercise is followed by its answer. Work it out on paper before reading the answer.

Exercise 1: the cheapest pair

Three towns 0, 1 and 2 have these one-way roads: 0 -> 1 costs 5, 1 -> 2 costs -2, and 0 -> 2 costs 4. Find dist[0][2].

Show the answer

The value is 3. The direct road costs 4. The route through town 1 costs 5 + (-2) = 3. The smaller value wins, so dist[0][2] is 3.

Exercise 2: is the start on a loop?

In the negative cycle example, the loop is B -> C -> B. Town A (index 0) has no incoming roads. Does A lie on a negative cycle? What value is on its diagonal?

Show the answer

No. A cycle through A would need a road that comes back into A, and there is none. The diagonal value for A stays 0, which the table shows.

Exercise 3: two towns in a loop

Two towns, 0 and 1, have roads 0 -> 1 costing -1 and 1 -> 0 costing -1. Run the algorithm by hand, with k equal to 0 and then k equal to 1. Which diagonal values are negative at the end?

Show the answer

Both are negative. At k equal to 0, dist[1][1] becomes dist[1][0] + dist[0][1], which is -1 + -1 = -2. At k equal to 1, dist[0][0] becomes dist[0][1] + dist[1][0], which is -2. Then dist[1][1] becomes dist[1][1] + dist[1][1], which is -4, because the same cell is read twice. So at the end dist[0][0] is -2 and dist[1][1] is -4.

Exercise 4: why INF is not the maximum

Explain in your own words why INF is set to the largest long long divided by 4, and not to the largest long long.

Show the answer

Two INF values are added during the update step. If INF is the full maximum, the sum overflows the type and wraps to a negative value, so an unreachable pair looks like a very cheap route. Dividing by 4 leaves room for a sum of two INF values, and the result still counts as huge.

Exercise 5: check the example by hand

Using the three-town example with A to B costing 4, A to C costing 5 and C to B costing -3, find the cheapest cost from A to B, and the route that gives it.

Show the answer

The cost is 2, and the route is A -> C -> B. The direct road costs 4, and the route through C costs 5 + (-3) = 2, which is smaller.

Summary

• Floyd-Warshall fills an n by n table of costs with three nested loops, and the outer loop is the allowed stop k.
• The update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) only runs when both halves are known, so INF must be skipped.
• After the loops, a negative value on the diagonal means that vertex lies on a negative cycle, and the other cells cannot be trusted.
• Choose INF so that adding two of them cannot overflow, and check the diagonal after each step to stop early.
• The algorithm is simplest for small or dense graphs. For large sparse graphs, Dijkstra from each vertex is usually faster.