Floyd-Warshall Calculator

Pseudocode

Three nested loops and one line of update. The subtlety is entirely in the loop order: k must be the outermost loop, and getting that wrong is the classic bug.

FloydWarshall(graph):
    dist = V by V matrix, all infinity
    for each vertex v:     dist[v][v] = 0
    for each edge (u,v,w): dist[u][v] = w

    for k in vertices:              // intermediate
        for i in vertices:          // source
            for j in vertices:      // target
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    next[i][j] = next[i][k]   // for path reconstruction

    // Negative cycle iff dist[v][v] < 0 for some v

The invariant is that after the iteration for k, dist[i][j] is the shortest path from i to j using only vertices from the first k as intermediates. k has to be outermost for that to hold: it is what expands the set of permitted waypoints one at a time. Putting k innermost still terminates and still produces plausible numbers, which is precisely what makes the bug so hard to catch.

Worked example, step by step

Run Floyd-Warshall on a small directed graph and watch one entry improve twice as the set of allowed intermediates grows.

Example graph: Directed edges A to B (3), A to C (8), B to C (2), B to D (7), C to D (1).

1. Initialise. Direct edges only. From A: B is 3, C is 8, D is unreachable. From B: C is 2, D is 7. From C: D is 1. Every diagonal entry is 0.
2. k = A. Nothing changes. No edge points into A, so dist[i][A] is infinite for every other i and no path can route through A.
3. k = B. Two improvements. dist[A][C] drops from 8 to dist[A][B] + dist[B][C] = 3 + 2 = 5. dist[A][D] falls from infinity to 3 + 7 = 10, the first finite route from A to D.
4. k = C. Two more. dist[A][D] improves again, from 10 to dist[A][C] + dist[C][D] = 5 + 1 = 6, and note this uses the value of dist[A][C] that k = B just improved. dist[B][D] drops from 7 to 2 + 1 = 3.
5. k = D. Nothing changes, since D has no outgoing edges and cannot serve as an intermediate.

Final distances from A are B 3, C 5, D 6. The A to D entry improved twice, from infinity to 10 to 6, which shows the layering directly: the k = C pass could only find the better route because the k = B pass had already improved A to C. That dependency is why k must be the outer loop.

Complexity, and where it comes from

Time: O(V^3) · Space: O(V^2)

Three nested loops over all vertices give exactly V cubed iterations, each doing constant work. There is no early exit and no dependence on the number of edges, so the algorithm costs the same on a sparse graph as on a dense one. Space is the V by V distance matrix, plus a second matrix if you want to reconstruct paths rather than just their lengths. In practice V cubed is fine up to a few thousand vertices; at 5,000 it is 125 billion operations and running Dijkstra from every vertex, at O(V·E·log V), becomes the better choice on sparse graphs.

When to use Floyd-Warshall Algorithm, and when not to

Floyd-Warshall wins on density and simplicity, and loses badly on sparse graphs at scale.

Common pitfalls

• Putting the k loop anywhere but outermost. This is the defining Floyd-Warshall bug. With k inner, the invariant breaks and the result is silently too large for some pairs. It produces no error and looks reasonable, so it survives casual testing. The order must be k, then i, then j.
• Adding to infinity. If infinity is represented as a large integer, dist[i][k] + dist[k][j] overflows and wraps to a negative number, creating shortest paths that do not exist. Guard the addition, or use a sentinel small enough that doubling it cannot overflow.
• Running it on a graph with a negative cycle without checking. The algorithm does not fail, it just returns meaningless values. After the loops, any vertex with dist[v][v] below zero lies on a negative cycle. Check that before trusting the matrix.
• Using it on a large sparse graph. V cubed ignores E entirely. On a graph with 10,000 vertices and 30,000 edges, Floyd-Warshall does a trillion operations while Dijkstra from each vertex does a few hundred million.
• Forgetting to initialise the diagonal. dist[v][v] must start at 0, not infinity. Leaving it infinite breaks the very first relaxations and quietly corrupts everything downstream.

Frequently asked questions

What is the Floyd-Warshall algorithm used for?

It computes shortest paths between every pair of vertices in a weighted graph in one run. It is used for all-pairs distance tables in route planning, computing the transitive closure of a relation, finding a graph diameter, detecting currency arbitrage across all pairs at once, and any situation where you will query many different source-target pairs.

What is the time complexity of Floyd-Warshall?

O(V cubed) time and O(V squared) space, with no dependence on the number of edges. Three nested loops run over all vertices with constant work inside, and there is no early termination. This makes it insensitive to density, which is an advantage on dense graphs and a serious disadvantage on sparse ones.

Why must k be the outermost loop?

Because k represents the set of vertices allowed as intermediates, and the algorithm grows that set one vertex at a time. After the pass for a given k, every entry is correct using only the first k vertices as waypoints. If k is not outermost that invariant never holds, and the algorithm returns distances that are too large without any error.

Can Floyd-Warshall handle negative weights?

Yes, negative edges are fine as long as there is no negative cycle. After the algorithm finishes, a negative value on the diagonal, dist[v][v] below zero, means v lies on a negative cycle and the distances involving it are meaningless.

When should I use Dijkstra instead of Floyd-Warshall?

When the graph is sparse and weights are nonnegative. Running Dijkstra from each vertex costs O(V·E·log V), which on a graph with far fewer than V squared edges is dramatically faster than V cubed. Floyd-Warshall wins on dense graphs, on small graphs, and when you want the shortest possible implementation.