Algorithm Deep Dive: Floyd-Warshall Algorithm

A Bit of History

The familiar triple-loop pattern emerged through closely related work on reachability and shortest paths. Bernard Roy described a version in 1959; Stephen Warshall published the Boolean transitive-closure form in 1962; and Robert Floyd published “Algorithm 97: Shortest Path” that same year. This is why names such as Floyd–Warshall, Roy–Warshall, and Roy–Floyd–Warshall appear in different traditions. The deeper unity is algebraic: the same matrix update can combine reachability, distances, or other path summaries by changing the operations.

The DP State: What Has Been Allowed So Far?

Number the vertices $1,2,\ldots,V$. Define $d^{(k)}[i][j]$ as the shortest $i$-to-$j$ distance whose intermediate vertices may come only from $\{1,\ldots,k\}$. The endpoints $i$ and $j$ are not restricted by that set.

Endpoints

Every ordered pair $(i,j)$

One matrix cell represents one source–destination question. Directed pairs are distinct.

Stage k

Allowed intermediates

Stage $k$ adds one possible transfer point; it does not force the path to use that vertex.

Stored value

Best distance so far

A cell can only stay equal or decrease as more intermediates become legal.

Stage zero: direct travel only

$d^{(0)}[i][i]=0$.
$d^{(0)}[i][j]$ is the lightest direct edge $i\to j$ when one exists.
$d^{(0)}[i][j]=\infty$ when no direct edge exists.

Taking the minimum over parallel edges during initialization matters: the DP assumes the base matrix already contains the best route with no intermediate vertices.

The Recurrence: Skip k or Use k

Any best path allowed at stage $k$ falls into one of two cases. It either avoids $k$, so the old answer remains valid, or it uses $k$, in which case the path splits into an $i$-to-$k$ prefix and a $k$-to-$j$ suffix:

$$d^{(k)}[i][j]=\min\left(d^{(k-1)}[i][j],\ d^{(k-1)}[i][k]+d^{(k-1)}[k][j]\right)$$

The recurrence does not search every path explicitly. It classifies all newly legal paths by whether they use the newest intermediate vertex $k$.

Why k Must Be the Outermost Loop

The algorithm compresses the conceptual 3D table $d^{(k)}$ into one 2D matrix. The outer $k$ loop is the timeline: after its iteration, every cell must mean “intermediates through $k$ are allowed.” The $i$ and $j$ loops may be swapped, but moving $k$ inside them destroys that shared stage invariant and can leave some pairs using partially updated knowledge while others do not.

for k in vertices:          # expand the allowed intermediate set
    for i in vertices:      # choose a source
        for j in vertices:  # choose a destination
            if dist[i][k] != INF and dist[k][j] != INF:
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Loop Order Is Part of the Algorithm

Three loops over the same indices are not automatically equivalent. Keep $k$ outermost unless you are using a separately proved blocked or cache-optimized formulation.

Worked Example

Let $A\to B=3$, $B\to C=1$, and $A\to C=10$. Initially, only direct edges are allowed. When B becomes legal as an intermediate, the A-to-C cell discovers a cheaper two-edge route.

old direct valueimproved through B

Only the A-to-C cell changes in this stage. A later stage repeats the same comparison for every ordered pair using the next allowed intermediate.

Why the DP Recurrence Works

Invariant: after completing outer iteration $k$, the matrix contains the best distances whose intermediate vertices are drawn only from $\{1,\ldots,k\}$.

Base case. Before any outer iteration, a legal path has no intermediate vertices, so it is either the zero-length diagonal path or one direct edge. The initialization is therefore correct.

Inductive step. Consider a shortest $i$-to-$j$ path allowed at stage $k$. If it avoids $k$, its value is already $d^{(k-1)}[i][j]$. If it uses $k$, then—when no relevant negative cycle makes the optimum unbounded below—we can choose an optimal walk in which $k$ need not be repeated. Splitting at $k$ produces an optimal prefix $i\leadsto k$ and suffix $k\leadsto j$, each using only earlier intermediates. Their sum is the second recurrence candidate. Taking the smaller case proves the invariant.

Why one matrix is enough

During stage $k$, entries such as $d[i][k]$ and $d[k][j]$ cannot gain a useful improvement merely by inserting $k$ again when no negative cycle is involved: that would add a closed walk through $k$ of nonnegative cost. Reading an already updated stage-$k$ value is therefore harmless, which justifies the in-place 2D implementation.

Reconstructing Actual Paths

Distances answer “how much?” A next matrix answers “where do I go first?” Initialize next[u][v] = v for each direct edge. Whenever routing $i\to k\to j$ improves a cell, copy the first hop of the improved prefix:

next[i][j] = next[i][k]

To reconstruct $i\leadsto j$, repeatedly replace $i$ with next[i][j] until reaching $j$. If the distance is $\infty$, no path exists. If the pair is affected by a negative cycle, no finite shortest path exists and reconstruction must be rejected.

Detecting and Propagating Negative Cycles

After the main DP, $d[k][k]<0$ means some negative cycle is reachable from $k$ and can return to $k$. Any pair $(i,j)$ for which $i\leadsto k$ and $k\leadsto j$ can loop around that cycle arbitrarily many times before continuing, driving the route cost toward $-\infty$.

A Boolean Flag Is Not the Whole Story

A graph may contain a negative cycle that is irrelevant to some pairs. Mark exactly the affected pairs: for every negative-diagonal vertex $k$, any $(i,j)$ with finite $d[i][k]$ and $d[k][j]$ has distance $-\infty$ and no well-defined shortest path.

Complexity Analysis

The main computation considers all triples $(i,k,j)$:

$$\text{Time: } O(V^3) \qquad \text{Space: } O(V^2)$$

Maintaining a next matrix does not change these bounds. Explicitly marking all negative-cycle-affected pairs can add another $O(V^3)$ pass, still within the same asymptotic time.

The runtime does not benefit from sparsity: a graph with very few edges still pays for all $V^3$ triples. On the other hand, the regular matrix access pattern is simple, predictable, and often effective for modest or dense graphs. Blocked implementations can improve cache behavior without changing the recurrence.

Implementation

Each implementation keeps a distance matrix, a next-hop matrix, and an affected-pair matrix or set. It guards infinity before addition, keeps the lightest parallel edge, reconstructs finite paths, and rejects path requests whose cost is unbounded below.

State	Meaning	Update
`dist[i][j]`	Best distance under the current intermediate set	Take the smaller of the old value and the route through $k$
`next[i][j]`	First hop on the represented route	Copy `next[i][k]` when the route through $k$ wins
`affected[i][j]`	Whether a reachable negative cycle can lie on an $i$-to-$j$ walk	Mark after the main DP using negative diagonal entries
`INF`	No known route	Never add it to another distance

from math import isfinite

INF = float("inf")
NEG_INF = float("-inf")

def floyd_warshall(vertices, edges):
    """Return distance, next-hop, and negative-cycle-affected pairs."""
    vertices = list(dict.fromkeys(vertices))
    known = set(vertices)
    dist = {u: {v: (0 if u == v else INF) for v in vertices}
            for u in vertices}
    next_hop = {u: {v: (u if u == v else None) for v in vertices}
                for u in vertices}

    for u, v, weight in edges:
        if u not in known or v not in known:
            raise ValueError("every edge endpoint must be listed")
        if not isinstance(weight, (int, float)) or not isfinite(weight):
            raise ValueError("edge weights must be finite numbers")
        if weight < dist[u][v]:
            dist[u][v] = weight
            next_hop[u][v] = v

    for k in vertices:
        for i in vertices:
            if dist[i][k] == INF:
                continue
            for j in vertices:
                if dist[k][j] == INF:
                    continue
                candidate = dist[i][k] + dist[k][j]
                if isinstance(candidate, float) and not isfinite(candidate):
                    raise OverflowError("distance arithmetic overflowed")
                if candidate < dist[i][j]:
                    dist[i][j] = candidate
                    next_hop[i][j] = next_hop[i][k]

    negative_vertices = [k for k in vertices if dist[k][k] < 0]
    affected = {
        (i, j)
        for k in negative_vertices
        for i in vertices if dist[i][k] != INF
        for j in vertices if dist[k][j] != INF
    }
    for i, j in affected:
        dist[i][j] = NEG_INF
        next_hop[i][j] = None

    return dist, next_hop, affected

def reconstruct_path(source, target, dist, next_hop, affected):
    if (source, target) in affected:
        raise ValueError("no finite shortest path: negative cycle affects pair")
    if dist[source][target] == INF:
        return None
    path = [source]
    current = source
    for _ in range(len(next_hop)):
        if current == target:
            return path
        current = next_hop[current][target]
        path.append(current)
    raise RuntimeError("invalid next-hop matrix")

vertices = ["A", "B", "C"]
edges = [("A", "B", 3), ("B", "C", 1), ("A", "C", 10)]
dist, next_hop, affected = floyd_warshall(vertices, edges)
print(dist["A"]["C"])  # 4
print(reconstruct_path("A", "C", dist, next_hop, affected))
# ['A', 'B', 'C']

#include <algorithm>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>
using namespace std;

const long long INF = numeric_limits<long long>::max() / 4;
const long long NEG_INF = -INF;

struct Edge { int from, to; long long weight; };
struct Result {
    vector<vector<long long>> dist;
    vector<vector<int>> next;
    vector<vector<bool>> affected;
};

long long checkedAdd(long long a, long long b) {
    if (b > 0 && a > INF - b) throw overflow_error("distance overflow");
    if (b < 0 && a < NEG_INF - b) throw overflow_error("distance overflow");
    return a + b;
}

Result floydWarshall(int n, const vector<Edge>& edges) {
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    vector<vector<int>> next(n, vector<int>(n, -1));
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
        next[i][i] = i;
    }
    for (const Edge& e : edges) {
        if (e.from < 0 || e.from >= n || e.to < 0 || e.to >= n)
            throw invalid_argument("edge endpoint out of range");
        if (e.weight <= NEG_INF || e.weight >= INF)
            throw invalid_argument("edge weight outside safe range");
        if (e.weight < dist[e.from][e.to]) {
            dist[e.from][e.to] = e.weight;
            next[e.from][e.to] = e.to;
        }
    }

    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; ++j) {
                if (dist[k][j] == INF) continue;
                long long candidate = checkedAdd(dist[i][k], dist[k][j]);
                if (candidate < dist[i][j]) {
                    dist[i][j] = candidate;
                    next[i][j] = next[i][k];
                }
            }
        }

    vector<vector<bool>> affected(n, vector<bool>(n, false));
    for (int k = 0; k < n; ++k) if (dist[k][k] < 0)
        for (int i = 0; i < n; ++i) if (dist[i][k] != INF)
            for (int j = 0; j < n; ++j) if (dist[k][j] != INF)
                affected[i][j] = true;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) if (affected[i][j]) {
            dist[i][j] = NEG_INF;
            next[i][j] = -1;
        }
    return {dist, next, affected};
}

vector<int> reconstructPath(int source, int target, const Result& result) {
    if (result.affected[source][target])
        throw logic_error("negative cycle affects this pair");
    if (result.next[source][target] == -1) return {};
    vector<int> path{source};
    int current = source;
    for (size_t step = 0; step < result.next.size(); ++step) {
        if (current == target) return path;
        current = result.next[current][target];
        path.push_back(current);
    }
    throw logic_error("invalid next-hop matrix");
}

int main() {
    Result result = floydWarshall(3, {{0, 1, 3}, {1, 2, 1}, {0, 2, 10}});
    cout << "Distance A->C: " << result.dist[0][2] << " Path:";
    for (int v : reconstructPath(0, 2, result)) cout << ' ' << char('A' + v);
    cout << '\n';  // Distance A->C: 4 Path: A B C
}

import java.util.*;

class FloydWarshall {
    static final long INF = Long.MAX_VALUE / 4;
    static final long NEG_INF = -INF;

    record Edge(int from, int to, long weight) {}
    record Result(long[][] dist, int[][] next, boolean[][] affected) {}

    static long checkedAdd(long a, long b) {
        if (b > 0 && a > INF - b)
            throw new ArithmeticException("distance overflow");
        if (b < 0 && a < NEG_INF - b)
            throw new ArithmeticException("distance overflow");
        return a + b;
    }

    static Result solve(int n, List<Edge> edges) {
        long[][] dist = new long[n][n];
        int[][] next = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
            Arrays.fill(next[i], -1);
            dist[i][i] = 0;
            next[i][i] = i;
        }
        for (Edge edge : edges) {
            if (edge.from() < 0 || edge.from() >= n
                    || edge.to() < 0 || edge.to() >= n)
                throw new IllegalArgumentException("edge endpoint out of range");
            if (edge.weight() <= NEG_INF || edge.weight() >= INF)
                throw new IllegalArgumentException("edge weight outside safe range");
            if (edge.weight() < dist[edge.from()][edge.to()]) {
                dist[edge.from()][edge.to()] = edge.weight();
                next[edge.from()][edge.to()] = edge.to();
            }
        }

        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    if (dist[k][j] == INF) continue;
                    long candidate = checkedAdd(dist[i][k], dist[k][j]);
                    if (candidate < dist[i][j]) {
                        dist[i][j] = candidate;
                        next[i][j] = next[i][k];
                    }
                }
            }

        boolean[][] affected = new boolean[n][n];
        for (int k = 0; k < n; k++) if (dist[k][k] < 0)
            for (int i = 0; i < n; i++) if (dist[i][k] != INF)
                for (int j = 0; j < n; j++) if (dist[k][j] != INF)
                    affected[i][j] = true;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) if (affected[i][j]) {
                dist[i][j] = NEG_INF;
                next[i][j] = -1;
            }
        return new Result(dist, next, affected);
    }

    static List<Integer> reconstructPath(int source, int target, Result result) {
        if (result.affected()[source][target])
            throw new IllegalStateException("negative cycle affects this pair");
        if (result.next()[source][target] == -1) return List.of();
        List<Integer> path = new ArrayList<>();
        path.add(source);
        int current = source;
        for (int step = 0; step < result.next().length; step++) {
            if (current == target) return path;
            current = result.next()[current][target];
            path.add(current);
        }
        throw new IllegalStateException("invalid next-hop matrix");
    }

    public static void main(String[] args) {
        Result result = solve(3, List.of(
            new Edge(0, 1, 3), new Edge(1, 2, 1), new Edge(0, 2, 10)
        ));
        System.out.println("Distance A->C: " + result.dist()[0][2]);
        System.out.println("Path: " + reconstructPath(0, 2, result));
        // Distance A->C: 4; Path: [0, 1, 2]
    }
}

Real-World Applications

Floyd–Warshall is attractive when the vertex set is modest, many or all pairwise answers are needed, and a matrix is a natural representation.

Distance oracle

Precomputed routing costs

Compute every latency, transfer cost, or hop-adjusted route among a modest set of hubs, then answer pair queries in $O(1)$ time.

Graph metrics

Diameter and centrality inputs

An all-pairs matrix directly supports eccentricity, diameter, average distance, and closeness-style measurements when unreachable pairs are handled explicitly.

Reachability

Boolean transitive closure

Replace minimum with OR and addition with AND. The same stage invariant then answers whether every ordered pair is connected by some path.

State spaces

Small dense transition systems

For a compact set of states with many transitions, precomputing every best transition cost can simplify later planning and analysis.

The semiring perspective

Ordinary shortest paths use “min” to choose between routes and “plus” to concatenate route costs. Reachability uses OR and AND. This substitution reveals Floyd–Warshall as a general closure pattern rather than a trick tied only to numeric distances.

Choosing an All-Pairs Shortest-Path Algorithm

Method	Edge restrictions	Typical time	Best fit
Floyd–Warshall	Negative edges allowed; report affected pairs if cycles are negative	$O(V^3)$	Modest or dense graphs; simple matrix implementation
Repeated Dijkstra	Nonnegative weights	$O(V(E+V)\log V)$ with binary heaps	Large sparse graphs
Johnson	Negative edges allowed, but no negative cycles	$O(VE\log V)$ for sparse graphs with binary heaps	Sparse graphs needing all pairs
Repeated BFS	Unweighted edges	$O(V(V+E))$	Unweighted sparse graphs

There is no universal vertex threshold: language overhead, graph density, cache behavior, query volume, and memory limits all matter. Benchmark representative inputs instead of relying on a single folklore cutoff.

Pitfalls & Debugging

Symptom	Likely cause	Fix
Some multi-hop routes remain too large	$k$ is not the outer loop	Restore the stage order `for k`, then `for i`, then `for j`
Huge or negative nonsense values appear	Infinity was added, or fixed-width addition overflowed	Guard both subpaths before addition and use a safe sentinel or bounded arithmetic
A diagonal starts positive	Initialization copied a self-edge over the empty path	Initialize $d[i][i]=0$ and take the minimum with any explicit self-edge
Parallel edges produce the wrong base case	The last input edge overwrote a cheaper one	Initialize with the minimum weight for each ordered pair
Paths loop forever	Negative-cycle-affected pairs were sent to reconstruction	Propagate affected pairs and reject them before following next hops
An undirected graph behaves as directed	Only one direction of each input edge was initialized	Add both $u\to v$ and $v\to u$ explicitly

Unreachable and Unbounded Are Different

$+\infty$ means no route exists. $-\infty$ means routes exist but no finite minimum does, because a usable negative cycle can be repeated. Keeping these states distinct prevents subtle downstream errors.

Exercises

Build the Intuition by Stages

Trace: Add an edge $C\to A=2$ to the worked example and write the matrix after each outer-loop vertex.
Reconstruct: Hand-simulate the next updates that produce the path A → B → C.
Break it: Find a graph on which moving $k$ to the innermost loop leaves an incorrect distance.
Diagnose: Add a negative cycle reachable from A but disconnected from another vertex D. Identify exactly which ordered pairs should become $-\infty$.
Generalize: Implement Boolean Warshall by replacing min/plus with OR/AND, then compare its matrix to repeated graph searches.
Measure: Benchmark Floyd–Warshall against repeated Dijkstra as graph density grows while $V$ stays fixed.

A compact mental model

Floyd–Warshall grows a permission set. At stage $k$, every matrix cell asks whether its best route should keep avoiding $k$ or split through $k$. The outer loop controls what paths are legal; the inner loops update every ordered pair under that shared rule.

Cookie Consent

Floyd-Warshall Algorithm

Contents

A Bit of History

The DP State: What Has Been Allowed So Far?

Every ordered pair $(i,j)$

Allowed intermediates

Best distance so far

Stage zero: direct travel only

The Recurrence: Skip k or Use k

Why k Must Be the Outermost Loop

Loop Order Is Part of the Algorithm

Worked Example

Why the DP Recurrence Works

Why one matrix is enough

Reconstructing Actual Paths

Detecting and Propagating Negative Cycles

A Boolean Flag Is Not the Whole Story

Complexity Analysis

Implementation

Real-World Applications

Precomputed routing costs

Diameter and centrality inputs

Boolean transitive closure

Small dense transition systems

The semiring perspective

Choosing an All-Pairs Shortest-Path Algorithm

Pitfalls & Debugging

Unreachable and Unbounded Are Different

Exercises

Build the Intuition by Stages

A compact mental model

Cookie Consent

Floyd-Warshall Algorithm

Contents

A Bit of History

The DP State: What Has Been Allowed So Far?

Every ordered pair $(i,j)$

Allowed intermediates

Best distance so far

Stage zero: direct travel only

The Recurrence: Skip k or Use k

Why k Must Be the Outermost Loop

Loop Order Is Part of the Algorithm

Worked Example

Why the DP Recurrence Works

Why one matrix is enough

Reconstructing Actual Paths

Detecting and Propagating Negative Cycles

A Boolean Flag Is Not the Whole Story

Complexity Analysis

Implementation

Real-World Applications

Precomputed routing costs

Diameter and centrality inputs

Boolean transitive closure

Small dense transition systems

The semiring perspective

Choosing an All-Pairs Shortest-Path Algorithm

Pitfalls & Debugging

Unreachable and Unbounded Are Different

Exercises

Build the Intuition by Stages

A compact mental model

Related Deep Dives

Graph Theory Series

Bellman-Ford Algorithm

A* Search

Warshall's Algorithm (Transitive Closure)