Bellman-Ford shortest paths: a practical tutorial

Bellman-Ford solves the single-source shortest-path problem for a weighted graph, returning the minimum total cost from one source vertex to every reachable destination. It is the algorithm to reach for when an edge can have a negative weight, such as a rebate applied after a freight journey. Unlike Dijkstra’s algorithm, Bellman-Ford does not assume every path cost is non-negative.

A journey from Parramatta to Circular Quay illustrates the model: locations are vertices and road links are edges, while travel time, tolls, or distance provide weights. In the Australian route-planning market, services compete on how well they balance live traffic, tolls, ferries, and roadworks; the geometrically shortest route often is not the quickest. Bellman-Ford turns such a weighted network into source-based route costs, provided the weights follow the graph’s rules.

When Bellman-Ford is the right tool

Bellman-Ford works on directed or undirected weighted graphs. For a directed graph, an edge (u, v, w) means that a path may travel from u to v at cost w; reverse travel requires a separate edge. In an undirected graph, the same edge can be traversed in either direction, so a negative edge creates an immediately repeatable cost reduction.

Road distances and travel times are normally positive, but business costs can include credits, refunds, or rebates. A delivery network might subtract a fuel rebate from one depot-to-depot leg, while a public transport operator could model a promotional fare. Such signs do not mean that a longer route is better; they mean the total weight must be minimised rather than maximised.

Melbourne’s tram routes add a useful local twist because one-way streets, interchanges, and service disruptions create several plausible paths between the same stops. During the arvo peak, a route planner may prefer a small detour to avoid a stalled connection. Bellman-Ford can optimise the numeric costs assigned to those links, although live predictions still need separate data and refresh logic.

How relaxation produces shortest paths

The algorithm keeps a distance label for every vertex and repeatedly relaxes each edge. Relaxation tests whether travelling from u to v through edge weight w improves the current route to v. Starting with distance zero at the source and infinity everywhere else, the procedure makes at most V - 1 passes, where V is the number of vertices.

for each vertex v:
    distance[v] = infinity
    predecessor[v] = none
distance[source] = 0

for pass from 1 to V - 1:
    changed = false
    for each edge (u, v, weight):
        if distance[u] is finite:
            candidate = distance[u] + weight
            if candidate < distance[v]:
                distance[v] = candidate
                predecessor[v] = u
                changed = true

for each edge (u, v, weight):
    if distance[u] is finite:
        if distance[u] + weight < distance[v]:
            report a reachable negative cycle

Each complete pass can reveal routes with one more edge than the previous pass. Edge order can change intermediate labels, so one ordering may settle faster than another, but the final distances are the same when no reachable negative cycle exists. The predecessor array records which predecessor produced each improvement, allowing a shortest path to be reconstructed after the search.

The predecessor update belongs inside a successful relaxation, not whenever an edge is merely examined. Otherwise, a reconstructed path may contain edges that never supported its label. If a complete pass changes nothing, another pass cannot reveal a new route, so the implementation can stop early.

Why V-1 passes are enough

The proof relies on path length. If no reachable negative cycle exists, removing a cycle cannot increase the path’s cost, so some shortest route uses at most V - 1 edges. After pass k, all routes using at most k edges have been accounted for, while every finite distance still represents a discovered path. By pass V - 1, an optimum has had enough opportunities to propagate through the graph.

One more relaxation can lower a distance only if a reachable negative cycle exists. Repeated travel around that cycle lowers the total cost without bound, which means no finite shortest path exists for its affected destinations. Vertices that cannot be reached from the source retain infinite distance and must not trigger cycle detection.

The V - 1 bound concerns finite shortest paths. With a reachable negative cycle, relevant labels can keep falling, so the algorithm should report that condition rather than return a misleading route.

A small graph worked by hand

Consider five vertices, A through E, with A as the source. The edges are A→B:4, A→C:2, C→B:-2, B→D:4, C→D:5, C→E:7, and D→E:-3. The negative edge makes the route through C preferable to the direct four-unit trip to B.

Scanning the edges in the listed order, the first pass produces A=0, B=0, C=2, D=4, and E=1. The second pass leaves those labels unchanged. The winning route is A → C → B → D → E, whose cost is 2 - 2 + 4 - 3 = 1. Predecessors reconstruct the route by walking backwards from E through D, B, C, and finally A.

Now add E→A:-2. The cycle A→C→B→D→E→A costs -1, so it can be traversed repeatedly to reduce the route cost indefinitely. A final detection pass finds that A can still improve and reports a reachable negative cycle.

A Python implementation with cycle detection

A compact Python implementation can represent every edge as a (source, target, weight) tuple. The graph does not need to be rebuilt between passes, and the final scan checks specifically for a further improvement after the distance-search phase.

from math import inf


class NegativeCycleError(ValueError):
    """Raised when a negative cycle is reachable from the source."""


def bellman_ford(
    vertex_count: int,
    edges: list[tuple[int, int, int]],
    source: int,
) -> tuple[list[float], list[int | None]]:
    if not 0 <= source < vertex_count:
        raise IndexError("source is outside the vertex range")

    distance: list[float] = [inf] * vertex_count
    predecessor: list[int | None] = [None] * vertex_count
    distance[source] = 0

    for _ in range(vertex_count - 1):
        changed = False
        for u, v, weight in edges:
            if distance[u] != inf:
                candidate = distance[u] + weight
                if candidate < distance[v]:
                    distance[v] = candidate
                    predecessor[v] = u
                    changed = True

        if not changed:
            break

    for u, v, weight in edges:
        if distance[u] != inf and distance[u] + weight < distance[v]:
            raise NegativeCycleError(
                "A negative cycle is reachable from the source"
            )

    return distance, predecessor

The exception is raised only when the edge’s source is reachable from the chosen start. That distinction matters in disconnected graphs: a negative cycle in another component does not invalidate finite distances in the source’s component. Type hints and explicit index checks can make the function safer in production.

Financial inputs deserve care. Integer Australian cents avoid binary floating-point ambiguity; for real-valued weights, define a comparison tolerance first. That numerical policy belongs beside the graph search, not inside its logic.

At a Perth mining operation, vertices might represent haul routes, processing sites, and rail connections, with rebates encoded as negative edge weights. If records are first ordered by bounded integer identifiers, the counting sort guide explains a linear-time ordering option; sorting remains optional for Bellman-Ford and does not replace the relaxation passes.

Dijkstra, Prim, and other graph algorithms

Dijkstra’s algorithm is often faster for a single source because it finalises the nearest unsettled vertex and stops exploring it. Its greedy choice relies on non-negative edge weights. Bellman-Ford trades speed for generality, accepting negative edges and identifying reachable negative cycles when required.

Prim’s algorithm solves a different optimisation problem: it builds a minimum spanning tree, connecting every vertex with the smallest total edge cost. A Prim’s algorithm tutorial on hello ML compares that tree-building process with other greedy methods. A shortest path optimises one source-to-destination sequence; a spanning tree connects all vertices and contains no cycles.

Queue-based variants such as the Shortest Path Faster Algorithm reinsert a changed vertex. They may be quick on many inputs, but their worst-case time remains O(VE). Floyd–Warshall is preferable for all-pairs distances when cubic time is acceptable.

Performance choices and production recommendations

Bellman-Ford uses O(VE) time in the worst case because it may scan every edge during each of V - 1 passes, plus one detection scan. The distance and predecessor arrays use O(V) auxiliary space; storing the input edges adds O(E) space. Runtime can improve with an early-stop flag when a pass makes no changes.

The choice among related algorithms depends on edge signs, graph size, and the number of source queries:

Criterion	Bellman-Ford	Dijkstra	Floyd–Warshall
Main goal	Distances from one source	Distances from one source	Distances between every pair
Negative edge weights	Supported	Not supported	Supported
Negative cycles	Detected when source-reachable	Not supported	Detected
Typical time	O(VE)	O((V + E) log V)	O(V^3)
Working space	O(V) auxiliary	O(V + E) with a lazy heap	O(V^2)
Strongest use	Signed costs and cycle checks	Large graphs with non-negative costs	Small graphs needing all-pairs answers

For production use, these recommendations cover the main implementation choices:

• Use Bellman-Ford when a reachable edge may carry a negative cost or a negative-cycle check is mandatory.
• Use Dijkstra when every edge is non-negative and the graph is large, since its greedy finalisation avoids repeated full scans.
• Keep the edge list unchanged during the distance passes; deterministic ordering also makes tests and debugging easier.
• Run the separate detection scan after the distance passes, and distinguish a source-reachable cycle from one in an unrelated component.
• Reconstruct routes with predecessor links, and handle infinite distances explicitly before traversing a predecessor chain.
• For repeated all-pairs questions involving negative edges, compare Bellman-Ford with Johnson’s algorithm rather than assuming repeated single-source runs will be cheap.

Bellman-Ford earns its extra work when negative costs encode genuine business rules, not simply because it is a familiar graph algorithm.