Floyd–Warshall all-pairs shortest paths

A small warehouse map answers route-cost questions between many pairs of loading bays throughout a shift. Running a fresh shortest-path search for every pair repeats work; the map is small enough to prepare a complete distance table.

Floyd–Warshall builds that table by allowing intermediate vertices one at a time. The outer loop has a meaning: it decides which stops the routes may use, rather than merely controlling the order of arithmetic.

Preparing routes between every loading bay

Floyd–Warshall grows the set of allowed intermediate vertices. At step k, compare the existing route i→j with i→k→j. The intermediate loop must remain outside the endpoint loops to preserve that subproblem order.

Allowing one more intermediate stop

With direct costs 0 → 1: 3, 1 → 2: 2, and 0 → 2: 9, allowing stop 1 improves the last route to five. For each pair, compare its existing cost with the cost via the newly allowed stop. Keep the intermediate-stop loop outside both endpoint loops; changing that order loses the staged dependency the update relies on.

value := func(n int) *int { return &n }
distance := [][]*int{
	{value(0), value(3), value(9)},
	{nil, value(0), value(2)},
	{nil, nil, value(0)},
}
for k := 0; k < 3; k++ {
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if distance[i][k] == nil || distance[k][j] == nil {
				continue
			}
			candidate := *distance[i][k] + *distance[k][j]
			if distance[i][j] == nil || candidate < *distance[i][j] {
				distance[i][j] = value(candidate)
			}
		}
	}
}
fmt.Println(*distance[0][2], distance[2][0] == nil) // 5 true

Knowing when the full matrix is worthwhile

Initialize diagonal zero and keep the cheapest parallel edge. Skip additions containing unreachable values. A negative diagonal afterward detects any negative cycle, including one in a disconnected component. O(V³) time and O(V²) storage suit modest dense graphs and all-pairs queries. Build private working state. The Go API uses nil for absence and assumes finite cost arithmetic fits int.

The matrix updates cost O(V³) time and require O(V²) storage; reading the input edges is additional work. A repeated single-source baseline can cost more on dense graphs, but a sparse graph may suit repeated Dijkstra when weights are nonnegative. Any negative cycle is relevant to an all-pairs request.

The warehouse gets cheap later lookups by accepting the cost of preparing and storing every pair.