Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Floyd-Warshall for all-pairs shortest paths

Shortest-path questions often begin with a single source: what is the quickest route from my house to work, or which path reaches this train station first? A shortest-path tree serves queries from one source, whereas an all-pairs shortest-path algorithm finds the minimum cost between every ordered pair of vertices in a weighted graph. That broader result is valuable when many origins and destinations share the same road, rail or flight network, and it avoids repeating a single-source search once for each departure point.

The Floyd-Warshall algorithm tackles that problem with dynamic programming and a compact distance matrix. It can handle negative edge weights, provided no reachable negative cycle exists, and it works with either directed or undirected graphs. Its assumptions are simple, but its usefulness depends on choosing it at the right graph size and treating edge weights as a consistent measure.

How the recurrence finds every shortest path

Imagine a graph in which vertices are stations and weighted edges are direct journeys. A distance of zero on the diagonal means a journey from a place to itself costs nothing; infinity means there is no known direct connection. Initialise other entries with direct edge costs, then ask whether a route through another vertex is cheaper. This is the central idea of Floyd-Warshall: improve known paths by admitting one possible intermediate vertex at a time.

Mathematically, let d[i,j] hold the best distance currently known from i to j. For each intermediate vertex k, update every pair using:

$$ d[i,j] \leftarrow \min(d[i,j],\ d[i,k] + d[k,j]). $$

Before the update, the two terms on the right describe paths whose internal vertices come from the set already processed. After it, they also allow k. The recurrence is a shortest-path analogue of dynamic programming for matrix multiplication. The same pattern on Boolean weights, using logical OR and AND, computes a transitive closure instead of distances.

The intermediate-vertex loop must be outermost. With vertices numbered zero to V - 1, processing k = 0 permits that vertex as an intermediate point, then k = 1 permits the next, and so on. After the final pass, all vertices are legal intermediates. The running time is O(V³), while the distance matrix uses O(V²) space. The hello ML collection of community-written tutorials is a useful place to connect this graph method with other programming and optimisation topics.

Building a weighted graph in Python

Choose a graph representation that matches the question. For undirected connections, insert an edge in both directions; for one-way streets or timetabled services, use a directed edge. A missing edge must be infinity rather than zero, because zero would create an artificial free journey. If parallel edges exist, retain the smallest weight. Keep all weights in one unit: kilometres for distance, minutes for travel time or currency for cost.

Here is a small Python implementation that returns a nested dictionary keyed by vertex names:

def floyd_warshall(vertices, edges):
    index = {name: i for i, name in enumerate(vertices)}
    n = len(vertices)
    inf = float("inf")
    dist = [[inf] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, weight in edges:
        i, j = index[u], index[v]
        dist[i][j] = min(dist[i][j], weight)

    for k in range(n):
        for i in range(n):
            if dist[i][k] == inf:
                continue
            for j in range(n):
                if dist[k][j] == inf:
                    continue
                through_k = dist[i][k] + dist[k][j]
                if through_k < dist[i][j]:
                    dist[i][j] = through_k

    return {
        u: {v: dist[index[u]][index[v]] for v in vertices}
        for u in vertices
    }

Using abstract vertices A, B and C, suppose A-B costs 4, B-C costs 3 and A-C costs 10. The result for A to C becomes 7 because the two-leg path is cheaper. The diagonal remains zero unless a negative cycle is present. This implementation assumes consistent weights and does not silently discard unrecognised vertex names, so a mapping error should be fixed rather than interpreted as a disconnected graph.

Why Australian travel networks make a useful example

Australian travel provides concrete examples of why graph structure matters. Sydney’s Opal system is used across trains, buses, light rail and ferries, while Melbourne’s Myki system is used on trains, trams and buses. Each mode can be a vertex type or a separate station, and a transfer becomes an edge. A planner must then decide whether an edge represents a single service, a walk between platforms, or a fare-adjusted transfer.

Distance also changes the scale of the problem. Perth is roughly 4,000 road kilometres from Sydney and about 2,700 kilometres from Adelaide, so intercity route comparisons involve very different geographic costs. Drivers keep to the left, roundabouts dominate suburban intersections, and some regional highways carry road trains. These features influence real journeys, yet a static shortest-path model still needs fixed weights; live traffic, time-of-day fares and missed connections generally call for a time-dependent model rather than one distance matrix.

Australian delivery businesses and marketplace couriers face the same graph questions on a smaller scale: which vehicle takes which order, and which sequence minimises travel or fuel cost. Many use route planners or fleet software to compare those choices. Personal journey records add another constraint. The Privacy Act 1988 and the Australian Privacy Principles govern how organisations handle identifiable information, so operational card data should not be treated as automatically public or safe to publish.

What the method proves and where it breaks

The correctness argument is an induction over the permitted intermediate vertices. Before any pass, the matrix correctly represents paths with no internal vertices: direct edges and zero-length journeys. When vertex k becomes allowed, an optimal path either avoids k, so its distance is already stored, or passes through k once, splitting into two paths using only earlier intermediates. Taking the smaller of the stored distance and the sum covers both cases. With no negative cycle, repeating k cannot improve the result, so in-place updates are safe.

Negative edges are allowed, but a reachable negative cycle is not. Such a cycle lets a traveller reduce the journey cost indefinitely, and the notion of a shortest distance becomes meaningless. After the algorithm finishes, a negative diagonal entry, d[i,i] < 0, flags this condition. An undirected negative edge also creates a two-edge negative cycle. Zero-weight edges and non-negative cycles pose no problem because traversing them cannot reduce the total cost.

The method is particularly attractive for a modest, dense graph where every vertex may act as a hub. On a large sparse graph, running Dijkstra’s algorithm from each vertex can be faster because it avoids the full cubic scan. Johnson’s algorithm is another option when a sparse graph has negative edges but no negative cycles. Some delivery problems go beyond path finding and ask how to allocate vehicles subject to capacity and time limits. That is a linear programme, and the Simplex method offers a related optimisation approach; Floyd-Warshall supplies distances but does not allocate vehicles or build schedules.

Practical guidance for reliable implementations

Implementation details matter because a mathematically valid graph can still produce misleading answers. A transport dataset may label one edge as walking time and another as driving time, or accidentally combine kilometres with minutes. A cost model may also need a common currency for fuel and tolls. Confirm the units, direction of travel and meaning of every edge before solving. The same care applies to graphs used in LeetCode exercises: make zero mean a genuine zero-weight edge, not a missing connection, and test the diagonal as well as off-diagonal results.

A concise checklist covers the choices that cause most errors: