Bellman-Ford and bounded paths

Problem

You want cheapest paths in a weighted graph where Dijkstra's greedy rule is not allowed: some edges are negative, or the question limits how many edges a path may use, or you must notice that costs can fall forever around a loop. The cheapest route may even be a longer one with more edges, which is exactly what the greedy settled-set argument cannot handle.

Intuition

Start with only the source known, at cost 0. A path with one edge from the source is found by looking at each edge once. A path with two edges is found by looking at each edge again, now that the first edge's far end has a cost. So each full pass over the edge list teaches the graph about paths one edge longer. A shortest path that avoids repeating a node has at most n - 1 edges, so n - 1 passes always suffice, and no cleverness about order is needed.

That also tells you how to impose a limit. If the cheapest route using at most 3 edges is what you want, run 3 passes and stop. The only care is to make each pass read the numbers from the end of the previous one, not from a table already updated in this pass, or a path can sneak in extra edges during one pass.

Every edge points from the first node listed to the second; the thick edge is the negative one. The diagram scrolls sideways on a narrow screen.

Mechanics

Relaxing an edge

To relax edge (u, v, w): if dist[u] + w < dist[v], set dist[v] to that smaller value. Unreached nodes hold infinity and are skipped. A round relaxes every edge once.

Invariant and proof

After round r, dist[v] is at most the cost of the cheapest path from the source to v that uses at most r edges (and is never below the true shortest distance, since it is always the cost of some real path). Induction on r: the cheapest path with r edges is a cheapest path with r - 1 edges to some node u, plus the edge (u, v); round r relaxes that edge using the round r - 1 value. A simple path has at most n - 1 edges, so after n - 1 rounds all shortest distances are final.

Negative cycles

If a cycle's total cost is negative and the source can reach it, going around again always lowers the cost, so no finite shortest distance exists and rounds never stop improving. Run one more round after n - 1: if any edge still relaxes, a reachable negative cycle exists. To find negative cycles anywhere in the graph, start all distances at 0 instead of only the source.

Bounding the number of edges

For "at most k stops" the path may use k + 1 edges. Run exactly k + 1 rounds, with each round writing to a copy so every edge read sees only paths from the previous round. Reading from the same table you are writing lets one round chain several edges, which breaks the limit.

Blue cells changed in that round. With the edges listed in the worst order, only one new link in the chain settles per round.

Worked example

On the graph above the edges are processed in the order given, from node 0. The table below shows the distances after each round (∞ means not reached yet). After round 4 they are 0, -1, 1, 2, 4, and round 5 changes nothing, so the algorithm stops. Node 1 first appears at 4 by the direct edge, then drops to -1 in round 2 once node 2 (at 1) relaxes the negative edge 2 → 1. Dijkstra happens to get this graph right, because it settles node 2 before node 1; the Dijkstra page shows a graph where a negative edge reaches a node it has already settled.

Cheapest flights. Flights 0→1 (100), 1→2 (100), 2→0 (100), 1→3 (600), 2→3 (200), from city 0 to city 3: with 0 stops the answer is -1 (no direct flight), with 1 stop it is 700 (via city 1), and with 2 stops it is 400 (via cities 1 and 2).

The copy matters. Allow one round (0 stops) with the flights in this order. Reading from a copy gives a price to city 3 of inf, which is correct: city 3 is unreachable in one flight. Updating in place lets 0 → 1, then 1 → 2, then 2 → 3 all happen in a single pass, reporting 400, which uses three flights.

A negative cycle. Edges 0→1 (1), 1→2 (-3), 2→1 (1): the loop 1 → 2 → 1 costs -2 each time. After 3 rounds (n) the distances still fall, so the answer is "negative cycle: True".

Implementation

INF = float("inf")

def bellman_ford(n, edges, source):
    dist = [INF] * n
    dist[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None  # a negative cycle is reachable
    return dist


def find_cheapest_price(n, flights, src, dst, k):
    prices = [INF] * n
    prices[src] = 0
    for _ in range(k + 1):
        nxt = prices[:]
        for u, v, w in flights:
            if prices[u] != INF and prices[u] + w < nxt[v]:
                nxt[v] = prices[u] + w
        prices = nxt
    return -1 if prices[dst] == INF else prices[dst]

Variations and edge cases

def has_negative_cycle(n, edges):
    dist = [0] * n
    for _ in range(n):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            return False
    return True


from collections import deque

def spfa(n, graph, source):
    # queue-based speedup: re-relax only nodes whose distance just dropped
    dist = [INF] * n
    dist[source] = 0
    queue, queued = deque([source]), {source}
    while queue:
        u = queue.popleft()
        queued.discard(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if v not in queued:
                    queue.append(v)
                    queued.add(v)
    return dist

• Copy per round for edge limits. Without the copy, one round may chain many edges.
• Skip unreached nodes. Adding a weight to infinity is harmless in Python floats but guard it anyway so integer sentinels do not overflow.
• Early exit. If a round changes nothing, later rounds cannot either; stop. Do not use that rule for the exact-k edge case, where fewer rounds is a different question.
• Stops versus edges. k stops means k + 1 edges (flights). A common off-by-one is running k rounds.
• Undirected negative edges form a negative cycle immediately (go back and forth), so treat them as directed or reject them.
• Edge cases: source equals target, unreachable target (return the "not possible" value), k = 0, and parallel edges.

Complexity and tradeoffs

• Time: O(V · E) for the full run; O(k · E) when limited to k rounds.
• Space: O(V) for the distance list, plus another O(V) for the per-round copy.
• Baseline. Enumerating paths is exponential. For non-negative weights Dijkstra is faster; this is the price paid for allowing negative edges and edge limits.
• Versus Dijkstra with state. Cheapest Flights can also be solved by Dijkstra over states (city, stops used), which can be faster on sparse graphs; Bellman-Ford is shorter to write and clearly correct.
• When it fails. With a reachable negative cycle there is no shortest path, only a report. All-pairs questions need Floyd-Warshall or Johnson's algorithm.

Problems

Cheapest Flights Within K Stops is the one list problem homed here: the stop limit turns the relaxation round count into the answer. Weighted problems with non-negative costs and no edge limit belong with Dijkstra.

Medium

• 787. Cheapest Flights Within K Stops Grind 169 NeetCode 150 NeetCode 250
  Run k+1 rounds of Bellman-Ford relaxation from a copy of the previous round, so no path uses more edges than allowed.

Connections

Bellman-Ford is Dijkstra without the greedy assumption, and dynamic programming in disguise: the table after round r is a DP over "best cost with at most r edges". The negative-cycle check is the same idea that powers currency-arbitrage detection.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 22.1 (the Bellman-Ford algorithm and its correctness proof).
• Bellman, "On a routing problem", Quarterly of Applied Mathematics 16, 1958; Ford, Network Flow Theory, RAND report P-923, 1956.
• Sedgewick and Wayne, Algorithms, section 4.4 (negative weights and cycles).
• Skiena, The Algorithm Design Manual, section on shortest paths.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.