All-Pairs Shortest Paths: Floyd–Warshall · Algorithms (DAA)

Dijkstra and Bellman–Ford find shortest paths from one source. Floyd–Warshall finds them between all pairs in one go, works with negative edges (but not negative cycles), and is just three nested loops.

The idea

Number the vertices 1 … n. Let dᵏ[i][j] be the shortest distance from i to j using only vertices 1 … k as intermediate stops. Either the best path avoids vertex k, or it goes through k:

dᵏ[i][j] = min( dᵏ⁻¹[i][j], dᵏ⁻¹[i][k] + dᵏ⁻¹[k][j] )

Start with d⁰ = the edge weights (∞ where there is no edge, 0 on the diagonal). After k = n, every vertex has been allowed as an intermediate: the matrix holds all shortest distances. The table can be updated in place.

A directed graph with 4 vertices used in the program below.

C++

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int INF = 1e9;

void print(const vector<vector<int>> &d, int k) {
    cout << "after k = " << k << ":" << endl;
    for (auto &row : d) {
        for (int x : row) cout << setw(5) << (x >= INF ? string("inf") : to_string(x));
        cout << endl;
    }
}

int main() {
    int n = 4;
    vector<vector<int>> d = {
        {0,   3,   INF, 7},
        {8,   0,   2,   INF},
        {5,   INF, 0,   1},
        {2,   INF, INF, 0}};
    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][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        if (k == 0 || k == n - 1) print(d, k + 1);
    }
    bool negCycle = false;
    for (int i = 0; i < n; i++) if (d[i][i] < 0) negCycle = true;
    cout << "negative cycle: " << (negCycle ? "yes" : "no") << endl;
    return 0;
}

Output

after k = 1:
    0    3  inf    7
    8    0    2   15
    5    8    0    1
    2    5  inf    0
after k = 4:
    0    3    5    6
    5    0    2    3
    3    6    0    1
    2    5    7    0
negative cycle: no

Try it Yourself

Time Θ(V³), space Θ(V²). It is the best choice for dense graphs or when you need every pair. A negative value on the diagonal at the end means a negative cycle.

Warshall's algorithm: transitive closure

Replace min and + with OR and AND to answer "is there any path from i to j?". The result is the transitive closure of the graph — see Relations in Discrete Mathematics.

C++

#include <iostream>
using namespace std;

int main() {
    int n = 4;
    int R[4][4] = {{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}, {1, 0, 1, 0}};
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
    cout << "reachability matrix:" << endl;
    for (auto &row : R) { for (int x : row) cout << " " << x; cout << endl; }
    return 0;
}

Output

reachability matrix:
 1 1 1 1
 1 1 1 1
 0 0 0 0
 1 1 1 1

Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

1
What does Floyd–Warshall compute?
2
What is its time complexity?
3
How does Floyd–Warshall reveal a negative cycle?
4
In the recurrence, what does the outer loop variable k represent?

#The idea

#Warshall's algorithm: transitive closure

Test yourself

The idea

Warshall's algorithm: transitive closure