A Guide to Bellman-Ford for Shortest Paths with Negative Weights

Finding the shortest route through a graph usually brings Dijkstra’s algorithm to mind. It is fast and useful, but it relies on an important assumption: every edge weight must be zero or positive. When a graph contains penalties, credits, changing balances, or other negative values, that assumption breaks down. Learn more about Understanding The Bias Variance Tradeoff In Machine Learning.

The Bellman-Ford algorithm solves the single-source shortest-path problem while allowing negative edge weights. It can calculate the best known distance from one starting vertex to every reachable vertex and can report whether a reachable negative-weight cycle makes the result unreliable.

This makes Bellman-Ford a valuable algorithm for programming interviews, routing models, financial graphs, and learning material that connects graph theory with practical software. It is also a good example of how repeated local improvements can produce a globally correct answer.

For Australian examples, imagine a transport network connecting Sydney, Melbourne, Brisbane, and Perth, or a mining logistics graph around Western Australia. Edge weights might represent travel time, fuel cost, tolls, rebates, or a negative credit. The algorithm does not care whether the graph describes roads, data, or a fictional network; it cares about the weight rules.

Why Negative Weights Change the Problem

In a weighted directed graph, each edge has a source vertex, a destination vertex, and a numerical cost. A path’s total weight is the sum of all edge weights along it. A negative edge can reduce the cost of a path, which means taking an apparently longer route may lead to a cheaper result.

Dijkstra’s algorithm permanently selects the unvisited vertex with the smallest tentative distance. That decision is safe when future edges cannot reduce the selected distance. A negative edge invalidates this reasoning. A route that looks expensive early may later pass through a negative edge and become the true shortest path.

Bellman-Ford takes a more cautious approach. Rather than finalising vertices greedily, it repeatedly examines every edge and improves destination distances whenever a cheaper route is found. This extra work makes it slower, but it allows negative values.

For example, a route from Perth to a regional mine might include a subsidy represented by −8. A path with an earlier cost of 20 could eventually become 12 after that rebate. An algorithm that committed too soon could miss this improvement.

The Core Idea: Edge Relaxation

The central operation is called relaxation. For an edge from u to v with weight w, suppose the current best distance to u is dist[u]. If travelling through that edge produces a smaller value than dist[v], update it:

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

The source vertex starts with distance zero. Every other vertex starts at infinity, meaning it is not yet known to be reachable. Bellman-Ford then relaxes all edges repeatedly.

After one complete pass, the algorithm can correctly account for shortest paths that use at most one edge. After two passes, it can account for paths using at most two edges. In general, after V - 1 passes, where V is the number of vertices, all shortest simple paths have been considered.

A shortest path without a negative cycle never needs to repeat a vertex. If it did, removing the repeated section would produce a path that is no more expensive, unless the repeated section had a negative total weight. That special case is precisely a negative cycle, which must be handled separately.

How Bellman-Ford Proceeds

The algorithm begins by setting the source distance to 0 and all other distances to infinity. It then performs up to V - 1 rounds over the edge list. During each round, every edge gets an opportunity to propagate a shorter distance forward.

The order of edges does not affect correctness, although it can affect how quickly useful values spread during a pass. In some graphs, an improvement can travel across many edges within one iteration because of the chosen edge order. The formal guarantee still uses V - 1 rounds.

An early-stop optimisation is safe. If a complete pass makes no changes, no later pass can improve any distance, so the algorithm can return immediately. This often makes simple examples and sparse practical graphs much faster than the worst-case bound suggests.

Consider edges A → B with weight 4, B → C with weight −6, and A → C with weight 3. The direct route to C costs 3, while the route through B costs −2. Bellman-Ford first records the direct option, then discovers the cheaper route through the negative edge.

Pseudocode And Python Implementation

A compact version of the algorithm uses a list of triples, with each triple storing (start, end, weight). This representation is convenient because Bellman-Ford must scan every edge rather than repeatedly search for neighbouring vertices.

bellman_ford(vertices, edges, source):
    distance = infinity for every vertex
    distance[source] = 0

    repeat |vertices| - 1 times:
        changed = false

        for (u, v, weight) in edges:
            if distance[u] is not infinity:
                candidate = distance[u] + weight
                if candidate < distance[v]:
                    distance[v] = candidate
                    changed = true

        if changed is false:
            break

    for (u, v, weight) in edges:
        if distance[u] is not infinity and distance[u] + weight < distance[v]:
            report reachable negative cycle

    return distance

The infinity check matters. Without it, the program could try to add a weight to an unreachable value. In Python, float("inf") behaves naturally for comparisons, but the guard still makes the logic explicit and prevents meaningless arithmetic.

A useful implementation checklist can keep the code reliable:

• Initialise only the chosen source with distance zero.
• Perform at most V - 1 relaxation passes.
• Skip edges whose starting vertex is unreachable.
• Run one extra scan to test for a negative cycle.
• Use a predecessor map when the actual route must be reconstructed.

Here is a direct Python implementation:

def bellman_ford(vertices, edges, source):
    distance = {vertex: float("inf") for vertex in vertices}
    predecessor = {vertex: None for vertex in vertices}
    distance[source] = 0

    for _ in range(len(vertices) - 1):
        changed = False

        for start, end, weight in edges:
            if distance[start] == float("inf"):
                continue

            candidate = distance[start] + weight
            if candidate < distance[end]:
                distance[end] = candidate
                predecessor[end] = start
                changed = True

        if not changed:
            break

    for start, end, weight in edges:
        if (distance[start] != float("inf")
                and distance[start] + weight < distance[end]):
            raise ValueError("Reachable negative-weight cycle detected")

    return distance, predecessor

The predecessor dictionary records the previous vertex whenever a distance improves. Starting from a destination and following predecessors backwards reconstructs its shortest route. Reverse that collected sequence to obtain the forward path.

Detecting Negative-Weight Cycles

A negative-weight cycle is a loop whose edge weights add to a value below zero. For example, a cycle with weights 5, −3, and −4 has a total of −2. Repeating it makes the path cheaper without limit, so there is no finite shortest distance for vertices reachable after that cycle.

The detection step is simple: after V - 1 passes, scan every edge once more. If an edge can still be relaxed, a reachable negative cycle exists. The word “reachable” is important. A negative cycle in a disconnected part of the graph does not affect shortest paths from the selected source.

A negative cycle does not always mean the entire graph is unusable. Distances to vertices that cannot be reached from the cycle may remain well-defined. Production software may therefore mark affected vertices separately, especially when the graph models credit transfers, exchange rates, or resource balances.

For an undirected graph, a negative edge requires extra care. Traversing that edge in both directions creates a two-edge cycle with a negative total, so ordinary shortest-path assumptions fail immediately. If the problem is undirected, confirm whether negative weights are allowed before choosing Bellman-Ford.

Complexity And Practical Trade-Offs

With V vertices and E edges, Bellman-Ford has time complexity O(VE) and space complexity O(V) when the edge list is stored separately. The edge list itself requires O(E) storage, so the complete memory footprint is commonly described as O(V + E).

This is slower than Dijkstra’s typical O((V + E) log V) implementation with a binary heap, but the comparison is meaningful only when Dijkstra’s non-negative-weight requirement is satisfied. For dense graphs or very large networks, the difference can be substantial. For small graphs, Bellman-Ford’s straightforward logic may be preferable.

The following situations help distinguish the algorithms:

• Choose Bellman-Ford when negative edge weights may occur.
• Choose Dijkstra when every edge weight is non-negative and speed matters.
• Choose breadth-first search when every edge has equal cost.
• Consider Floyd-Warshall when shortest paths are needed between every pair of vertices.
• Use a topological-order dynamic programme for weighted directed acyclic graphs.

The graph’s structure also affects practical performance. A sparse road network may have far fewer edges than a dense relationship graph. In a large Australian logistics system spanning ports, rail terminals, and mine sites, representing only real connections rather than every possible pair can make the edge list manageable.

Testing Shortest-Path Results

Good tests should check more than a successful example. Include a graph with a negative edge but no negative cycle, an unreachable vertex, a disconnected negative cycle, and a reachable negative cycle. These cases verify both the distance calculations and the safety checks.

It is useful to compare the returned predecessor chain with the reported distance. Add the weights along the reconstructed path and confirm that the sum equals the stored shortest distance. This catches mistakes where distances are updated correctly but predecessor information is not.

When using examples based on Australian services, model the weights clearly. A Sydney public transport connection might use minutes, while a Perth freight route might use dollars or fuel units. Mixing units in one graph can produce technically valid arithmetic but meaningless results.

A final testing checklist includes:

• Confirm the source distance is exactly zero.
• Confirm unreachable vertices remain infinite.
• Verify a route containing a negative edge beats a more expensive direct route.
• Test that a reachable negative cycle raises or reports an error.
• Check reconstructed paths against their calculated total weights.

Choosing The Algorithm In Real Projects

Bellman-Ford is especially useful when edge weights represent adjustments rather than physical distance. A graph of currency conversions may contain rates transformed into negative logarithms, while a scheduling graph may use bonuses or penalties. Network configuration systems can also model gains and costs that are not naturally non-negative.

For learners, the algorithm provides a clear bridge between graph theory and broader machine learning concepts, where iterative updates and carefully defined objective values appear frequently. The same habit of distinguishing assumptions from guarantees is useful across programming and data science.

The surrounding explanation matters as much as the code. An open educational resource such as the hello ML background can help place algorithm tutorials within a wider community learning context, rather than treating implementation as a collection of isolated tricks.

In an Australian workplace, a team might prototype a route model for a Melbourne delivery network, a Brisbane infrastructure project, or a Western Australian mining operation. Before deployment, developers should confirm whether negative values represent legitimate credits or indicate bad input. Clear validation, cycle reporting, and documented units make the result far easier to trust.