Bellman-Ford and Negative Weights

Dijkstra settles a node as soon as it has the smallest tentative distance, and it assumes no later route can improve it. That assumption relies on every edge weight being non negative, because a negative edge could make a route through a node you have already passed come out cheaper. With a negative edge, the node you settled can turn out not to be settled at all, and the algorithm returns wrong distances.

Bellman-Ford makes no such assumption. It relaxes every edge of the graph repeatedly, one pass at a time, and after enough passes every shortest distance is correct. A shortest path uses at most V minus one edges, so V minus one passes are always sufficient.

The mechanism is that each pass propagates one more edge of any path. After the first pass, all paths of one edge are correct, after the second all paths of two edges, and so on, so after V minus one passes every shortest path has been accounted for.

The trade-off to name is the cost. Bellman-Ford runs in O of V E time, which is much worse than the heap version of Dijkstra. Its compensation is that it handles negative weights and can detect negative cycles, which Dijkstra cannot do at all. The other thing worth saying is that an early exit makes it much faster in practice: if a full pass changes nothing, the distances have converged and you can stop, which is usually the case when the graph is close to acyclic.

Initialise the source at zero and everything else at infinity, then relax every edge repeatedly until nothing changes or you have run enough passes.

def bellman_ford(n, edges, source):
    distance = [float('inf')] * n
    distance[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, weight in edges:
            if distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight
                changed = True
        if not changed:
            break
    return distance


edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3)]
print(bellman_ford(3, edges, 0))

The output is 0, 4 and 1. The cheapest route to node two is the direct edge of cost five or the route through node one, which costs four plus minus three, so the negative edge makes the indirect route cheaper.

The mechanism is that the first pass relaxes all three edges in order and node two ends up with the cost one, computed through node one. The second pass changes nothing, so the early exit fires and the algorithm stops. Without that early exit the algorithm would still be correct, it would just do useless work.

The trade-off to name is the pass count. V minus one passes are enough because a shortest path cannot repeat a node when all weights are non negative, and when negative weights exist but there is no negative cycle the same bound still holds. The cost of each pass is the number of edges, so the total is O of V E. The other detail is the infinity arithmetic: adding a weight to an infinite distance keeps it infinite, so unreachable nodes stay unreachable, but you must make sure the infinity value is a float and not something that would overflow when added to.