heyrian.dev
← Applied algorithms
Routes and connections When one route is not the question

Floyd–Warshall all-pairs shortest paths

Know every pair. Let each hub be the middle.

Graph libraries ship a function for the whole table at once. Python’s NetworkX sums up its floyd_warshall in one line: “Find all-pairs shortest path lengths using Floyd’s algorithm.”

We’ll fill that table for an electric delivery van in a hilly town: how much of the battery each trip uses, from every hub to every other, including a descent that puts charge back. Let’s watch it fill, one middle hub at a time.

TypeScriptGoOne battery matrix in each language

01 / The idea

The useful answer can be a whole table.

The direct road from Central to West climbs over the ridge and uses 20% of the van’s battery. Going round, Central → North → East → South → West, uses 5 + 3 + 4 + 2 = 14%. A dispatcher deciding which van can take which run needs numbers like that for every pair of hubs, and searching from one hub at a time repeats the same discoveries.

Floyd–Warshall computes the shortest path between every ordered pair in a weighted graph. It builds the table by allowing one more hub to sit in the middle of a route each round, reusing what the last round found.

Floyd–Warshall

Let every hub become the middle of a better route.

ALL-PAIRS BATTERY MATRIX · % OF A CHARGE 0 / 6 intermediates
Dnew[i,j]←minD[i,j],D[i,k] + D[k,j]
from \ toCentralNorthEastSouthWestIsland
Central0512∞20∞
North∞0315∞∞
East∞704∞∞
South∞∞∞02∞
West8∞-1∞0∞
Island∞∞∞∞∞0

Direct links are the starting matrix.

changed this round carried forward unreachable

01/ 03
Seed direct links

Seed direct links

Put 0 on the diagonal, keep each direct leg’s battery use, and leave missing pairs as ∞. The descent from West to East is −1: it puts a point back. No route has been composed yet.

Reduced motion: choose a scene to see its completed state.

Read this scene

Put 0 on the diagonal, keep each direct leg’s battery use, and leave missing pairs as ∞. The descent from West to East is −1: it puts a point back. No route has been composed yet.

Direct links only. The diagonal is 0 and missing pairs are ∞.

Watch and Step through replay the same matrix updates. Try it runs the TypeScript implementation on the hubs, an unreachable pair, or the hubs with one leg logged with the wrong sign.

The matrix is directional: West → Central uses 8%, while Central → West uses 14%. West → East is −1 because the road down puts a point back through regenerative braking. Island has a 0 on the diagonal because staying put costs nothing, and ∞ everywhere else because no road reaches it.

02 / Name the rule

Ask whether this hub makes the pair cheaper.

Let D[i,j] be the least battery known from i to j. When k is the next allowed middle hub, compare the old route with the route that goes through k:

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

If either half is ∞, there is no route through k. If the sum is smaller, replace the cell and remember the first hop, so a number can become an actual route.

Seed

Direct legs and zero

The diagonal starts at 0, each direct leg fills its cell, and every other pair starts at ∞.

Compose

One middle at a time

Each round tries every i, j through the same k. The code copies the previous round so each change is visible; updating in place gives the same answers.

Remember

The first hop

Distances answer “how much?” and next-hop links answer “which way?” without storing every path.

Why is this dynamic programming?The state is a set of allowed middle hubs

After round k, every route whose middle hubs come from the first k allowed has been considered. The next round reuses the previous table twice, once for i → k and once for k → j, so it never lists whole paths. There are exponentially many walks, but only V³ steps.

A leg below zero is a fact. A loop below zero is no answer.

The descent from West to East is −1 and is safe: no loop on this map puts back more than it uses. But suppose the climb from East to West is logged as −3 instead of 3. Then West → East → West gains 4 points every lap, and going round again makes any route through it cheaper without limit. The diagonal goes negative, and the code refuses the whole matrix.

No van gains charge driving in a circle, so the refusal points at bad data. Don’t replace it with a very large number or keep whichever value came last; the reading has to be fixed.

CHECK THE DIAGONALD[i,i] < 0

After every hub has been allowed in the middle, a negative diagonal means a negative cycle.

03 / Read the shape

Three loops, one matrix, and a first hop for every cell.

Basic form validates the graph and runs the recurrence. In the wild reads one ordered pair out of the finished result by following next hops, so one run answers every later question. At the call site prints the finished matrix, with a negative cell and ∞ side by side, then shows the mis-signed reading being refused.

Validate the directed legs between hubs, seed the matrix, and allow each hub as an intermediate. A composed route that uses less battery replaces a cell and records its first hop.

TypeScriptReading
distances.ts
export const MAX_NODES = 32;
export const MAX_EDGES = 128;
export const MIN_CHARGE = -50;
export const MAX_CHARGE = 100;

// charge is percentage points of the battery a leg uses. A downhill leg can put charge back
// through regenerative braking, so its charge can be negative.
export type Edge = { from: string; to: string; charge: number };
export type Network = { nodes: string[]; edges: Edge[] };
export type Update = {
	from: string;
	to: string;
	via: string;
	oldCharge: number | null;
	newCharge: number;
};
export type Round = {
	via: string;
	updates: Update[];
	distances: Record<string, Record<string, number | null>>;
};
export type AllPairs = {
	nodes: string[];
	distances: Record<string, Record<string, number | null>>;
	next: Record<string, Record<string, string | null>>;
	rounds: Round[];
};

export type FloydErrorCode =
	'too-big' | 'bad-node' | 'unknown-node' | 'bad-charge' | 'duplicate-edge' | 'negative-cycle';

export class FloydError extends Error {
	readonly code: FloydErrorCode;
	constructor(code: FloydErrorCode, message: string) {
		super(message);
		this.name = 'FloydError';
		this.code = code;
	}
}

type Matrix = (number | null)[][];
type NextMatrix = (number | null)[][];

function validate(network: Network): Map<string, number> {
	if (
		network.nodes.length === 0 ||
		network.nodes.length > MAX_NODES ||
		network.edges.length > MAX_EDGES
	)
		throw new FloydError('too-big', `use 1–${MAX_NODES} nodes and at most ${MAX_EDGES} edges`);
	const indexes = new Map<string, number>();
	for (const [index, node] of network.nodes.entries()) {
		if (!/^[a-z][a-z0-9-]{0,23}$/.test(node) || indexes.has(node))
			throw new FloydError('bad-node', `node ids are unique lowercase slugs: ${node}`);
		indexes.set(node, index);
	}
	const seen = new Set<string>();
	for (const edge of network.edges) {
		if (!indexes.has(edge.from) || !indexes.has(edge.to))
			throw new FloydError(
				'unknown-node',
				`an edge names a node that does not exist: ${edge.from}, ${edge.to}`
			);
		if (!Number.isInteger(edge.charge) || edge.charge < MIN_CHARGE || edge.charge > MAX_CHARGE)
			throw new FloydError(
				'bad-charge',
				`charge is a whole number of battery points from ${MIN_CHARGE} to ${MAX_CHARGE}`
			);
		const key = `${edge.from}\0${edge.to}`;
		if (seen.has(key))
			throw new FloydError('duplicate-edge', `only one edge may connect ${edge.from} → ${edge.to}`);
		seen.add(key);
	}
	return indexes;
}

function copyMatrix(matrix: Matrix): Matrix {
	return matrix.map((row) => row.slice());
}

function copyNext(next: NextMatrix): NextMatrix {
	return next.map((row) => row.slice());
}

function snapshot(nodes: string[], matrix: Matrix): Record<string, Record<string, number | null>> {
	return Object.fromEntries(
		nodes.map((from, i) => [from, Object.fromEntries(nodes.map((to, j) => [to, matrix[i][j]]))])
	);
}

function nextSnapshot(
	nodes: string[],
	next: NextMatrix
): Record<string, Record<string, string | null>> {
	return Object.fromEntries(
		nodes.map((from, i) => [
			from,
			Object.fromEntries(nodes.map((to, j) => [to, next[i][j] === null ? null : nodes[next[i][j]]]))
		])
	);
}

export function directDistances(network: Network): Record<string, Record<string, number | null>> {
	const indexes = validate(network);
	const matrix: Matrix = network.nodes.map((_, i) =>
		network.nodes.map((__, j) => (i === j ? 0 : null))
	);
	for (const edge of network.edges) {
		const from = indexes.get(edge.from)!;
		const to = indexes.get(edge.to)!;
		if (matrix[from][to] === null || edge.charge < matrix[from][to]!)
			matrix[from][to] = edge.charge;
	}
	return snapshot(network.nodes, matrix);
}

// D[k][i][j] is the cheapest route from i to j whose intermediate nodes are drawn from
// nodes 0..k. Copying the previous matrix makes that recurrence visible in every round.
export function traceAllPairs(network: Network): AllPairs {
	const indexes = validate(network);
	const { nodes } = network;
	const matrix: Matrix = nodes.map((_, i) => nodes.map((__, j) => (i === j ? 0 : null)));
	const next: NextMatrix = nodes.map((_, i) => nodes.map((__, j) => (i === j ? i : null)));
	for (const edge of network.edges) {
		const from = indexes.get(edge.from)!;
		const to = indexes.get(edge.to)!;
		if (matrix[from][to] === null || edge.charge < matrix[from][to]!) {
			matrix[from][to] = edge.charge;
			next[from][to] = to;
		}
	}

	const rounds: Round[] = [];
	for (const [via, viaName] of nodes.entries()) {
		const previous = copyMatrix(matrix);
		const previousNext = copyNext(next);
		const updates: Update[] = [];
		for (let from = 0; from < nodes.length; from += 1) {
			for (let to = 0; to < nodes.length; to += 1) {
				const left = previous[from][via];
				const right = previous[via][to];
				if (left === null || right === null) continue;
				const candidate = left + right;
				const oldCharge = previous[from][to];
				if (oldCharge !== null && candidate >= oldCharge) continue;
				matrix[from][to] = candidate;
				const firstHop = previousNext[from][via];
				next[from][to] = firstHop;
				updates.push({
					from: nodes[from],
					to: nodes[to],
					via: viaName,
					oldCharge,
					newCharge: candidate
				});
			}
		}
		rounds.push({ via: viaName, updates, distances: snapshot(nodes, matrix) });
	}

	if (matrix.some((row, index) => row[index] !== null && row[index]! < 0))
		throw new FloydError(
			'negative-cycle',
			'a negative cycle has no finite all-pairs distance matrix'
		);

	return {
		nodes: nodes.slice(),
		distances: snapshot(nodes, matrix),
		next: nextSnapshot(nodes, next),
		rounds
	};
}

export const allPairs = traceAllPairs;
GoAlongside
distances.go
const (
	MaxNodes    = 32
	MaxEdges    = 128
	MinCharge   = -50
	MaxCharge   = 100
	missingNext = ""
)

// Charge is percentage points of the battery a leg uses. A downhill leg can put charge back
// through regenerative braking, so its charge can be negative.
type Edge struct {
	From   string
	To     string
	Charge int
}

type Network struct {
	Nodes []string
	Edges []Edge
}

type Update struct {
	From      string
	To        string
	Via       string
	OldCharge *int
	NewCharge int
}

type Round struct {
	Via       string
	Updates   []Update
	Distances map[string]map[string]*int
}

type AllPairs struct {
	Nodes     []string
	Distances map[string]map[string]*int
	Next      map[string]map[string]string
	Rounds    []Round
}

type FloydError struct {
	Code    string
	Message string
}

func (e *FloydError) Error() string { return e.Message }

var nodePattern = regexp.MustCompile(`^[a-z][a-z0-9-]{0,23}$`)

func validate(network Network) (map[string]int, error) {
	if len(network.Nodes) == 0 || len(network.Nodes) > MaxNodes || len(network.Edges) > MaxEdges {
		return nil, &FloydError{Code: "too-big", Message: fmt.Sprintf("use 1–%d nodes and at most %d edges", MaxNodes, MaxEdges)}
	}
	indexes := make(map[string]int, len(network.Nodes))
	for index, node := range network.Nodes {
		if !nodePattern.MatchString(node) {
			return nil, &FloydError{Code: "bad-node", Message: fmt.Sprintf("node ids are unique lowercase slugs: %s", node)}
		}
		if _, exists := indexes[node]; exists {
			return nil, &FloydError{Code: "bad-node", Message: fmt.Sprintf("node ids are unique lowercase slugs: %s", node)}
		}
		indexes[node] = index
	}
	seen := make(map[string]bool, len(network.Edges))
	for _, edge := range network.Edges {
		if _, exists := indexes[edge.From]; !exists {
			return nil, &FloydError{Code: "unknown-node", Message: fmt.Sprintf("an edge names a node that does not exist: %s, %s", edge.From, edge.To)}
		}
		if _, exists := indexes[edge.To]; !exists {
			return nil, &FloydError{Code: "unknown-node", Message: fmt.Sprintf("an edge names a node that does not exist: %s, %s", edge.From, edge.To)}
		}
		if edge.Charge < MinCharge || edge.Charge > MaxCharge {
			return nil, &FloydError{Code: "bad-charge", Message: fmt.Sprintf("charge is a whole number of battery points from %d to %d", MinCharge, MaxCharge)}
		}
		key := edge.From + "\x00" + edge.To
		if seen[key] {
			return nil, &FloydError{Code: "duplicate-edge", Message: fmt.Sprintf("only one edge may connect %s → %s", edge.From, edge.To)}
		}
		seen[key] = true
	}
	return indexes, nil
}

func intPtr(value int) *int { return &value }

func copyMatrix(matrix [][]*int) [][]*int {
	copyOf := make([][]*int, len(matrix))
	for i, row := range matrix {
		copyOf[i] = append([]*int(nil), row...)
	}
	return copyOf
}

func copyNext(next [][]int) [][]int {
	copyOf := make([][]int, len(next))
	for i, row := range next {
		copyOf[i] = append([]int(nil), row...)
	}
	return copyOf
}

func snapshot(nodes []string, matrix [][]*int) map[string]map[string]*int {
	result := make(map[string]map[string]*int, len(nodes))
	for i, from := range nodes {
		result[from] = make(map[string]*int, len(nodes))
		for j, to := range nodes {
			if matrix[i][j] != nil {
				result[from][to] = intPtr(*matrix[i][j])
			} else {
				result[from][to] = nil
			}
		}
	}
	return result
}

func nextSnapshot(nodes []string, next [][]int) map[string]map[string]string {
	result := make(map[string]map[string]string, len(nodes))
	for i, from := range nodes {
		result[from] = make(map[string]string, len(nodes))
		for j, to := range nodes {
			if next[i][j] < 0 {
				result[from][to] = missingNext
			} else {
				result[from][to] = nodes[next[i][j]]
			}
		}
	}
	return result
}

// D[k][i][j] is the cheapest route from i to j whose intermediate nodes are drawn from
// nodes 0..k. Copying the previous matrix makes that recurrence visible in every round.
func TraceAllPairs(network Network) (AllPairs, error) {
	indexes, err := validate(network)
	if err != nil {
		return AllPairs{}, err
	}
	n := len(network.Nodes)
	matrix := make([][]*int, n)
	next := make([][]int, n)
	for i := range matrix {
		matrix[i] = make([]*int, n)
		next[i] = make([]int, n)
		for j := range next[i] {
			next[i][j] = -1
			if i == j {
				matrix[i][j] = intPtr(0)
				next[i][j] = i
			}
		}
	}
	for _, edge := range network.Edges {
		from := indexes[edge.From]
		to := indexes[edge.To]
		if matrix[from][to] == nil || edge.Charge < *matrix[from][to] {
			matrix[from][to] = intPtr(edge.Charge)
			next[from][to] = to
		}
	}

	rounds := make([]Round, 0, n)
	for via, viaName := range network.Nodes {
		previous := copyMatrix(matrix)
		previousNext := copyNext(next)
		updates := make([]Update, 0)
		for from := 0; from < n; from++ {
			for to := 0; to < n; to++ {
				if previous[from][via] == nil || previous[via][to] == nil {
					continue
				}
				candidate := *previous[from][via] + *previous[via][to]
				old := previous[from][to]
				if old != nil && candidate >= *old {
					continue
				}
				matrix[from][to] = intPtr(candidate)
				firstHop := previousNext[from][via]
				next[from][to] = firstHop
				var oldCopy *int
				if old != nil {
					oldCopy = intPtr(*old)
				}
				updates = append(updates, Update{From: network.Nodes[from], To: network.Nodes[to], Via: viaName, OldCharge: oldCopy, NewCharge: candidate})
			}
		}
		rounds = append(rounds, Round{Via: viaName, Updates: updates, Distances: snapshot(network.Nodes, matrix)})
	}

	for i := range matrix {
		if matrix[i][i] != nil && *matrix[i][i] < 0 {
			return AllPairs{}, &FloydError{Code: "negative-cycle", Message: "a negative cycle has no finite all-pairs distance matrix"}
		}
	}
	return AllPairs{
		Nodes:     append([]string(nil), network.Nodes...),
		Distances: snapshot(network.Nodes, matrix),
		Next:      nextSnapshot(network.Nodes, next),
		Rounds:    rounds,
	}, nil
}

var allPairs = TraceAllPairs
Reading the TypeScriptCopies, snapshots, and next hops

previous freezes the k − 1 table for one round. An accepted update writes the candidate into the working matrix and copies the first hop from i → k. The animation highlights those same updates; it is not a second algorithm.

Reading the GoNil cells mean ∞

Go uses nil pointers for unreachable matrix cells and an empty next-hop string when no route exists. The nested loops and negative-diagonal check follow the same contract as the TypeScript version.

What is refusedBounds and ambiguous input

Both examples cap the graph at 32 nodes and 128 directed edges, require lowercase unique node ids (bad-node), refuse an edge to a node that isn’t listed (unknown-node), reject duplicate directed edges (duplicate-edge), and take whole battery points from −50 to 100 (bad-charge). Opposite directions are separate edges. A negative diagonal is negative-cycle.

04 / Try a decision

Which loop goes outside?

The recurrence fits on one line, and the three loops look interchangeable. Decide before you reorder them.

A teammate moves the loop over middle hubs inside the other two: for each start, for each end, try each hub in the middle. Same recurrence, same starting matrix. What happens on the delivery map?

05 / Follow the cost

Every pair buys a cubic sweep.

Floyd–Warshall: time and extra space per operation
OperationTimeExtra spaceWhat it assumes
Seed direct linksO(V² + E)O(V²)Allocate the matrix, put 0 on the diagonal, and copy each direct edge into its cell.
Allow one intermediateO(V²)O(V²)Compare every ordered pair through the same middle node. The shown code copies the previous distance and next-hop matrices and snapshots the result for the animation; an in-place update needs O(1) extra.
Compute all pairsO(V³)O(V³)Run V matrix rounds. The shown trace keeps one V × V snapshot per round; without the snapshots it is O(V²), the size of the answer.
Rebuild one routeO(V)O(V)pathBetween reads a finished result: follow next-hop links until the target, with a guard against malformed cycles.
Repeated sparse searchO(V · (E + V) log V)O(V + E)Running Dijkstra once from every node may win on a sparse graph when all weights are zero or more.

With V nodes, the three nested loops cost O(V³), however few edges the graph started with. The matrix costs O(V²), which is also the size of the answer: if the caller needs every pair, the dense table isn’t overhead.

The shown trace stores one matrix snapshot per round for the animation, which makes its space O(V³). A production version keeps one matrix and updates it in place: row k and column k can’t improve during round k unless a negative cycle runs through k, so the answers match. Rebuilding a route afterwards is O(V), because pathBetween reads the finished result instead of running the matrix again.

06 / Give it a real job

Fill the table once, then answer every trip from it.

A dispatcher planning the day asks the same kind of question over and over: can the van at North, with 20% left, reach Central before it needs a charger? With the matrix filled, each answer is a lookup. North → Central uses 17% by the best route, so yes, with 3 points to spare, and pathBetween turns that number into the roads to take.

The planner refills the matrix when the map changes: a road closes, or new readings come in from the vans. That is also when a bad reading shows up. A leg logged with the wrong sign makes a loop that gains charge, the diagonal goes negative, and the planner refuses the new table and keeps yesterday’s until someone checks the reading.

It fits dozens of hubs, not a whole city’s streets. At a few thousand nodes, V³ is billions of steps; road-routing engines use other methods to answer many-to-many questions on big maps.

This runs in the planning service when the map changes; nothing in a component computes it.

07 / Make the call

Choose the question before the matrix.

Use Floyd–Warshall when the graph is small or dense and many pair questions justify the O(V²) table. Use Dijkstra when weights are zero or more and you need one start at a time. Use Bellman–Ford for one start with meaningful negative edges and a check for a loop that start can reach.

For a large sparse graph with no negative weights, running Dijkstra from every node often does less work than filling cells that stay ∞. Floyd–Warshall’s advantage is its short, predictable code and one computation that answers every ordered pair.

SourcesThe two 1962 papers and a library reference

All checked 23 September 2026.

08 / Take the idea with you

Explain a table of routes without saying “Floyd–Warshall.”

“Write down every direct trip, zero for staying put, and infinity for trips you can’t make directly. Then take one place at a time and ask, for every pair: is it cheaper to go through here? Keep the cheaper number and the first step. When every place has had its turn, the table is done, unless a place can reach itself for less than nothing.”

Before moving on, think of a question you answer for many pairs at once, like travel times between offices, and decide whether it wants one route or the whole table.

Connections to follow nextRelated lessons

Copy the complete example, remove the direct Central → West leg, and predict which matrix cells change when South is allowed in the middle.

Back to applied algorithms →