The Floyd–Warshall algorithm

Most shortest-path algorithms solve for distances from one vertex to the rest. Dijkstra and Bellman-Ford both start from a single source. For distances from every vertex to every other vertex, you could run Dijkstra V times, but that rebuilds the priority queue and adjacency list each time, and it fails entirely if any edge is negative.

Floyd-Warshall does not fix a source. It puts down a single distance matrix and runs one triple loop, and when it finishes the shortest distance for every pair is in the matrix. The code is twelve lines, it handles negative edges, and it reports whether a negative cycle exists.

The Core Idea

The whole algorithm repeats one question. Going from vertex i to j, does routing through vertex k make it shorter?

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

D[i][k] + D[k][j] is the length of going from i to k and then k to j. If that beats the D[i][j] known so far, it is updated. Applying this one line to every (i, j) pair, sweeping k from 1 to V, is the entire algorithm.

The allowed waypoints open up one at a time. At stage k=1, only vertex 1 may be used as a waypoint; at k=2, vertices 1 and 2; at k=V, every vertex is available. Once the final stage opens the full set of waypoints, the shortest distances are in place. This incremental expansion works because of optimal substructure: a subpath of a shortest path is itself a shortest path.

The 3D recurrence D[k][i][j] = min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j]) collapses to a 2D array, because at stage k the values D[i][k] and D[k][j] already equal the values for paths that don’t use k as a waypoint, so overwriting the same array is safe.

Loop Order

for k in 1..V:      # waypoint (must be outermost)
    for i in 1..V:  # source
        for j in 1..V:  # destination
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

The order must be k → i → j. If k moves inward, the premise of opening one waypoint at a time breaks and the answers come out wrong. k has to be outermost so that stage k uses only the results through stage k-1. The rest is mechanical.

One Run, Traced by Hand

A directed graph with four vertices and these edges:

Edges: 1→2(3), 1→3(8), 2→3(2), 2→4(5), 3→4(1)

The matrix trace below is the output of running the recurrence above as code.

Initial matrix (edges filled in, the rest INF, diagonal 0):

      1    2    3    4
1 [   0    3    8  INF ]
2 [ INF    0    2    5 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=1 (vertex 1 as waypoint): no path gets shorter through 1. No change.

k=2 (vertices 1, 2 as waypoints): paths through 2 open up.

• D[1][3] = min(8, D[1][2]+D[2][3]) = min(8, 3+2) = 5 (1→2→3)
• D[1][4] = min(INF, D[1][2]+D[2][4]) = min(INF, 3+5) = 8 (1→2→4)

      1    2    3    4
1 [   0    3    5    8 ]
2 [ INF    0    2    5 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=3 (vertices 1, 2, 3 as waypoints): going through 3 shrinks distances further.

• D[1][4] = min(8, D[1][3]+D[3][4]) = min(8, 5+1) = 6 (1→2→3→4)
• D[2][4] = min(5, D[2][3]+D[3][4]) = min(5, 2+1) = 3 (2→3→4)

      1    2    3    4
1 [   0    3    5    6 ]
2 [ INF    0    2    3 ]
3 [ INF  INF    0    1 ]
4 [ INF  INF  INF    0 ]

k=4: vertex 4 has no outgoing edges, so it is useless as a waypoint. No change. This is the final result. The shortest distance from 1 to 4 is 6, along the path 1→2→3→4.

Implementation

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

#define INF 1e9

int main() {
    int n, m; // n: number of vertices, m: number of edges
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));

    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0; // distance to self is 0
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], (long long)c); // take the minimum on duplicate edges
    }

    // triple loop -- k is outermost
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // negative-cycle check: a negative distance back to self means one exists
    bool hasNegativeCycle = false;
    for (int i = 1; i <= n; i++) {
        if (dist[i][i] < 0) { hasNegativeCycle = true; break; }
    }

    if (hasNegativeCycle) {
        cout << "A negative cycle exists." << '\n';
    } else {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF) cout << "INF ";
                else cout << dist[i][j] << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

The algorithm body is the triple loop itself; the mistakes happen around it.

• dist[i][i] = 0 initialization. Skip it and the distance to self stays INF, which breaks the negative-cycle check and corrupts the results.
• The dist[i][k] != INF && dist[k][j] != INF guard. Adding two INFs overflows into a negative number, so a nonexistent path masquerades as a short one. Check before adding.
• Duplicate edges. The same (a, b) can appear more than once, so take the minimum.
• Undirected graphs. Insert both (a, b) and (b, a).

Negative-Cycle Detection

Where Floyd-Warshall beats Dijkstra is negative edges. Dijkstra assumes a distance, once finalized, never shrinks again, which breaks on negative edges; Floyd-Warshall examines every waypoint combination exhaustively, so it stays correct even with negative edges.

A negative cycle is a cycle whose edge weights sum to a negative number. If A → B → C → A sums to -5, each loop drops the distance by another -5 (-5, -10, -15) without bound, so the shortest path is undefined.

Detection is simple: after the algorithm finishes, look at the diagonal. Normally the distance back to oneself, D[i][i], is 0. If a vertex sits on a negative cycle, its path back to itself accumulates negative weight, so D[i][i] < 0. A single O(V) scan is all it takes.

This property maps onto arbitrage detection. Convert each exchange rate r to -log(r), which turns the multiplication of rates into addition, and a negative cycle becomes a loop of currency conversions that yields risk-free profit.

Path Reconstruction

When distances aren’t enough and the actual path is needed, keep a next array alongside. next[i][j] is the vertex you step to right after i on the shortest path from i to j.

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

#define INF 1e9

void printPath(int i, int j, vector<vector<int>>& next) {
    if (next[i][j] == -1) { cout << "No path" << '\n'; return; }
    cout << i;
    while (i != j) {
        i = next[i][j];
        cout << " -> " << i;
    }
    cout << '\n';
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    vector<vector<int>> next(n + 1, vector<int>(n + 1, -1));

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            next[a][b] = b; // start with the directly connected vertex
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k]; // inherit the first step toward k
                }
            }
        }
    }

    printPath(1, n, next); // print the path from 1 to n
    return 0;
}

Updating next[i][j] = next[i][k] whenever the distance updates is the point. If the shorter route from i to j goes through k, its first step is the same as the first step of the route from i to k. To print, follow next and list the vertices in order. Applied to the graph above, the 1→4 path comes out as 1 -> 2 -> 3 -> 4. If path reconstruction might be needed, keep next from the start; bolting it on later means rerunning the algorithm.

What O(V³) Means, and Its Limit

The triple loop runs V times each, so the operation count is V³, and each operation (add, compare, update) is constant time. Space is the O(V²) distance matrix, and adding next stays at O(V²).

Because V enters as a cube, runtime climbs sharply past a few hundred vertices. Floyd-Warshall fits graphs with few vertices and dense edges.

If all pairs are needed and the graph is small, dense, or has negative edges, use Floyd-Warshall. For a single source, or many vertices with sparse edges and positive weights, Dijkstra is the better fit.