Bellman-Ford & Negative Weights
In short: Bellman-Ford finds cheapest costs on a graph that may have both
cycles and negative edges, by relaxing every leg, V − 1 times, in any
order. After round k, every stop's cost is at most the cheapest route to it
using at most k legs, so V − 1 rounds cover every simple route. One more
round that still improves something proves a reachable loop makes money —
there is no cheapest route to report, and the algorithm must say so.
The night timetable had credits but no loops, and one sweep handled it. Daytime Meridian is messier. Roads run both ways, so the network is full of cycles, and partner depots rebate a van that carries their returns: on the books, those legs cost less than nothing. The tariff router has to find the cheapest route through that, and there is a new danger. If a few rebate legs form a loop whose total is negative, a van could drive round it forever, getting paid each lap. Then "the cheapest route" doesn't exist, and the router must say so rather than print a number.
Neither tool you have works here. Dijkstra settles stops too early when a rebate can undercut them later, and the DAG sweep needs an order that a cyclic network doesn't have. Bellman-Ford needs neither. It settles nothing and assumes no order; it just relaxes every leg, again and again, until nothing moves.
Rounds, and what each one guarantees
One round relaxes every leg in the network once, in any order. The whole algorithm is V − 1 rounds, where V is the number of stops. The reason is one invariant:
After round k, every stop's cost is at most the cheapest route to it that uses at most k legs.
Round 1 prices every one-leg route out of the start. Round 2 extends the best of those by one more leg, and so on. And if no loop makes money, a cheapest route never needs to visit a stop twice, because cutting out the loop between the two visits can't make it dearer. A route with no repeated stop has at most V − 1 legs, so after V − 1 rounds every cheapest route has been priced.
Watch it on a small piece of the daytime network. The legs are relaxed in a deliberately unhelpful order (listed in the note), so it takes more than one round. Each note records the costs at the end of a round:
Each round relaxes every leg once. Costs only ever fall, and a round that changes nothing means every cost is final.
Only the depot has a cost. Every round will try all six legs in the order listed. 5 nodes, 6 edges, directed. At depot. depot: 0.
leg order: quay>yard, yard>harbour, depot>quay, depot>mill, mill>quay, mill>harbour
That last step is the detection rule. After V − 1 rounds, costs can only still fall if some loop keeps making them fall. So one extra round is a proof: if anything improves in round V, there is a money-making loop the start can reach.
Bellman-Ford in code
The loop is short. Keep a changed flag so a quiet round ends things early, then
spend one more pass over the legs checking for a loop:
Unreachable stops stay at infinity and cause no trouble: inf + cost is still
inf, so they never "improve" anything.
The order of legs inside a round never affects the final answer, but it does affect how many rounds you need:
legs = [["d", "e", 1], ["c", "d", 1], ["b", "c", 1], ["a", "b", 1]] # listed back to front
best = {"a": 0}
rounds = 0
while True:
rounds += 1
changed = False
for x, y, cost in legs:
if x in best and best[x] + cost < best.get(y, float("inf")):
best[y] = best[x] + cost
changed = True
if not changed:
break
print(rounds)That is also the difference between relaxing in place and relaxing from a snapshot of the previous round. In place, a lucky order can chain several new legs within one round. From a snapshot, round k means exactly "at most k legs", which is what you want when the number of legs is capped (the step-limited mix in the graphs section was this). Step through a snapshot round:
c stays unpriced: b only got its cost in new, and the round reads from best.
Trusting the answer
It's easy to write the rounds and forget the check. Then a money-making loop doesn't produce an error; it produces a confident, wrong number:
This network has a loop that pays the van every lap, so the harbour has no cheapest cost, but the function prints a number anyway. Make it return "loop" when round V would still improve something.
A loop only matters if it is net negative. One that exactly breaks even is
harmless, and the strict < is what makes the check agree:
legs = [["mill", "quay", 3], ["quay", "mill", -3]]
best = {"mill": 0, "quay": float("inf")}
for a, b, cost in legs: # V - 1 = 1 round
if best[a] + cost < best[b]:
best[b] = best[a] + cost
print(any(best[a] + cost < best[b] for a, b, cost in legs))The main task goes one step further than "is there a loop?". A loop only ruins the answer for stops it can reach. Any leg that still improves after V − 1 rounds marks its target as unbounded, and so is everything downstream of it. A loop in the far corner of the city shouldn't stop the router pricing a trip across the middle.
Your Bellman-Ford, drawn
Here is Bellman-Ford drawing each improvement as it happens, with a final check that
flags any leg still improving. Remove the ["yard", "mill", -5] leg to see a clean
run, or change it to -1 and work out by hand whether the loop still pays before
you press run.
Your Bellman-Ford. Badges only fall. If any leg can still lower one after V − 1 rounds, the costs have no floor.
How slow is "every leg, every round"?
V − 1 rounds of E legs is O(V × E). Dijkstra is O((V + E) log V). On a city-sized
network the gap is brutal, which is why real routers use Bellman-Ford only when
they must, and often just once, to check a tariff table or to compute the potentials
you'll meet in the next lesson. Memory is cheap by comparison: just the best
cost per stop, O(V) space — no heap, no per-round copy needed.
Say Meridian has n junctions and about 3n roads. Bellman-Ford does about 3n × n relaxations and Dijkstra about 4n × log₂ n heap steps, so Bellman-Ford does about 3n / (4 log₂ n) times the work:
| junctions n | Bellman-Ford's work over Dijkstra's |
|---|---|
| 1,000 | 75× |
| 10,000 | 564× |
| 19,000 | 1,003× |
| 1,000,000 | 37,629× |
A modest town of 19,000 junctions already costs a thousand times more, and the ratio grows almost linearly with the size of the network. Use Bellman-Ford when costs can be negative, and nowhere else.
A common speed-up keeps a queue of stops whose cost just fell and only relaxes legs out of those, since a leg out of an unchanged stop can't improve anything. On typical road networks it is much faster, though its worst case is no better.
Interview-style: exchange-board arbitrage
Meridian pays partner fleets in their own credit schemes: fuel vouchers, parking tokens, charge points. An exchange board lists rates such as "1 fuel voucher buys 2 parking tokens". Is there a cycle of exchanges that ends with more than you started with?
It doesn't look like a shortest-path problem: it multiplies instead of adding, and bigger is better. Two changes fix both. A logarithm turns a product into a sum, and a minus sign turns "bigger" into "smaller":
A profitable cycle is exactly a negative loop under weights −log r, and Bellman-Ford finds negative loops. The boss exercise builds it, including the floating-point tolerance that stops a break-even cycle like 2 × 0.5 from looking like profit.
What it costs
| Time | Handles | |
|---|---|---|
| DAG sweep | O(V + E) | negative costs, no cycles |
| Dijkstra | O((V + E) log V) | cycles, no negative costs |
| Bellman-Ford | O(V × E) | cycles and negative costs; detects money-making loops |
❓ Cross-question — "Why not add a big constant to every cost so none is negative, then use Dijkstra?" Because routes with more legs get charged the constant more times, so the ranking of routes changes. The reweighting that does work, a different adjustment per stop, is in the next lesson.
Quick practice
legs = [["d", "e", 1], ["c", "d", 1], ["b", "c", 1], ["a", "b", 1]]
best = {"a": 0}
for _ in range(2):
for x, y, cost in legs:
if x in best and best[x] + cost < best.get(y, float("inf")):
best[y] = best[x] + cost
print(best.get("d"))The chain a → b → c → d → e costs 4, but this prints inf. Fix the round count.
🎯 Your turn
Write tariff_route(legs, start, goal). legs is a directed edge list of
[from, to, cost], rebates are negative, and loops are allowed. Return
{"cost": total, "path": stops} for the cheapest route, {"cost": None, "path": []}
if the goal is unreachable, or {"cost": "loop", "path": []} if a money-making loop
reachable from the start can also reach the goal:
tariff_route([["depot", "mill", 2], ["depot", "quay", 6], ["quay", "mill", -5], ["mill", "harbour", 3]], "depot", "harbour")→{"cost": 4, "path": ["depot", "quay", "mill", "harbour"]}
Hint: V − 1 rounds with parent, one checking pass to find doomed stops, a
DFS to spread "doomed" downstream, then walk parent back from the goal.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Meridian's router is built. ✅