When a cheap route can get cheaper later

Picture

A negative edge can make a later detour cheaper than a route you wanted to finalize now. Bellman–Ford avoids Dijkstra’s commitment by repeatedly relaxing every edge. An edge-count bound explains how many passes suffice when no reachable negative cycle exists.

Predict

A route may use a reachable negative-total cycle any number of times before continuing to the destination. Is there a finite cheapest route to that destination?

Reveal the reasoning

No. Repeating the cycle keeps reducing cost, so the costs have no finite minimum. The cycle must be reachable from the source and able to reach that destination for this conclusion about that destination.

Go deeper: bounded path length replaces finalization

Without a reachable negative cycle, some shortest route to each reachable vertex can be simple and use at most V-1 edges: removing a nonnegative cycle does not worsen its cost. After each full relaxation pass, all routes with at most that many edges have been accounted for, possibly more because this implementation updates in place.

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

assert bellman_ford(3, [(0, 1, 4), (0, 2, 5), (2, 1, -3)], 0) == ([0, 2, 5], False)
assert bellman_ford(2, [(0, 1, 1), (1, 0, -2)], 0)[1]
assert not bellman_ford(3, [(1, 2, -1), (2, 1, -1)], 0)[1]

Assume n>=1, valid vertex labels, and finite integer edge weights. Infinity prevents unreachable vertices from offering finite routes, so an unreachable negative cycle does not raise this source-specific flag.

Time is O(VE) and auxiliary distance storage is O(V) excluding the input edge list. If the flag is true, the returned vector is an intermediate result, not a certified set of finite shortest distances. This compact API flags existence of a reachable negative cycle; marking exactly which vertices have unbounded distances requires propagating from affected vertices.

A DAG can instead relax edges once in topological order, even with negative weights, because no later dependency returns to a finished vertex. Match the algorithm to the strongest available guarantee.

Analogy limit: repeated improvement is not evidence of a finite optimum. The problem’s mathematics may permit arbitrarily low cost.

Change one rule

You seek the cheapest route using at most K edges, even if the graph contains negative cycles. Is that bound useful?

Check the variation

Yes. Use an edge-count layer: the next layer reads only the previous layer and also retains shorter routes. With finite K, you have a finite DP. In-place relaxation can inadvertently use multiple extra edges within one pass, so separate layers matter for this exact bound.

Connect

Evaluation order explains layered dependencies. Recognition uses costs, cycles, and path restrictions together, rather than choosing solely from the word “shortest.”