Bellman-Ford and choosing an algorithm

Why it matters

Dijkstra's algorithm from the previous lesson is fast, but it needs every edge cost to be zero or more. Real problems do not always fit that rule. A currency exchange can give you a small gain on each trade, which turns a cost into a negative number. A scheduling problem can say that one task must start at least a certain time before another, which is a negative constraint. An interview question can ask for the cheapest route with at most k flights, and then the usual shortest-path idea needs a twist.

Bellman-Ford handles negative edges. It is slower than Dijkstra, but it is simple, it is correct when there are no negative cycles, and it can tell you when a negative cycle makes the question meaningless. This lesson also gives you a table for choosing among all the graph algorithms in this module, which is what interviewers ask for at the end of a graph question. "Which algorithm would you use, and why?" is a common follow-up.

You should be comfortable with the previous four lessons. You will also use the idea of rounds from the dynamic programming module, which we explain here from the start.

Why a negative edge is harder

Think about a road that pays you a toll reward for driving on it. Each edge has a cost, but this edge makes the total smaller. Dijkstra's algorithm assumes that once a vertex is the cheapest unfinished one, no later route can beat it. A negative edge breaks that assumption. A route through a not-yet-explored vertex might subtract enough to undercut a vertex that Dijkstra already finished.

Bellman-Ford does not make that assumption. It does not finish vertices one at a time. Instead, it keeps improving every distance a little at a time, and it stops when nothing can be improved. This is slower, but it always gets the right answer as long as no cycle has a negative total.

The idea: relax every edge, many times

Bellman-Ford repeats one simple step over and over. Go through every edge a -> b with cost w. If dist[a] + w is less than dist[b], update dist[b] to that value. This is relaxing an edge, the same word used in Dijkstra. The difference is that Bellman-Ford relaxes every edge in every round, in any order, instead of picking the cheapest vertex first.

Why does this work? Think about the shortest path from the source to any vertex. If the path has no cycle, it visits each vertex at most once, so it has at most n - 1 edges. Each round of the loop over all edges makes sure that every shortest path with one more edge than before is found. Round 1 finds all shortest paths of one edge. Round 2 finds all shortest paths of at most two edges, and so on. After n - 1 rounds, every shortest path that has no cycle is found, so every distance is final.

Here is the idea as a rule you can check. After round k, the value dist[v] is at most the cost of the best path to v that uses at most k edges. That is a claim you can verify by induction, and it is the reason the algorithm must run exactly n - 1 rounds in the worst case.

A worked example by hand

Use a directed graph with five vertices and ten edges. The edges, in order, are 0 -> 1 (6), 0 -> 2 (7), 1 -> 2 (8), 1 -> 3 (5), 1 -> 4 (-4), 2 -> 3 (-3), 2 -> 4 (9), 3 -> 1 (-2), 4 -> 3 (7) and 4 -> 0 (2). Start at vertex 0. The distances start as dist[0] = 0 and every other vertex is infinity.

Round 1, the first pass over the edges in the order listed.

Edge 0 -> 1, cost 6: 0 + 6 = 6 is less than infinity, so dist[1] = 6.

Edge 0 -> 2, cost 7: dist[2] = 7.

Edge 1 -> 2, cost 8: 6 + 8 = 14 is not less than 7, so no change.

Edge 1 -> 3, cost 5: 6 + 5 = 11, so dist[3] = 11.

Edge 1 -> 4, cost -4: 6 - 4 = 2, so dist[4] = 2.

Edge 2 -> 3, cost -3: 7 - 3 = 4, which is less than 11, so dist[3] = 4.

Edge 2 -> 4, cost 9: 16 is not less than 2.

Edge 3 -> 1, cost -2: 4 - 2 = 2, which is less than 6, so dist[1] = 2.

Edge 4 -> 3, cost 7: 2 + 7 = 9, not less than 4.

Edge 4 -> 0, cost 2: 2 + 2 = 4, not less than 0.

After round 1, the distances are 0, 2, 7, 4, 2. Notice that dist[1] improved in the same round in which it was first set, because a later edge in the list gave a better route to it. The order of the edges does not change the final answer, only how many rounds it takes.

Round 2 makes one more change. Vertex 4 drops from 2 to -2, through the edge 1 -> 4 after 1 has already improved to 2. Round 3 changes nothing, so every distance is final. The program below uses that fact to stop early.

The final distances are 0, 2, 7, 4, -2. Vertex 4 ends at -2 through the route 0, 2, 3, 1, 4, which costs 7 - 3 - 2 - 4 = -2. That route has four edges, so it is within the n - 1 = 4 rounds the algorithm allows.

The animation below shows the same idea as a table of values, one step at a time.

The first program: distances with negative edges

The first program reads a directed graph and a source. It runs Bellman-Ford for n - 1 rounds, then checks whether one more pass can still improve a distance. It prints each distance, with unreachable for vertices no route reaches.

Type this into the Input box. The first line is n m s: five vertices, ten edges and source 0. Then the ten edges, each as a b w:

5 10 0
0 1 6
0 2 7
1 2 8
1 3 5
1 4 -4
2 3 -3
2 4 9
3 1 -2
4 3 7
4 0 2

The program prints:

dist[0] = 0
dist[1] = 2
dist[2] = 7
dist[3] = 4
dist[4] = -2
negative cycle reachable: no

The distances match the hand trace. The last line is the check. After the rounds are done, one more pass over the edges looks for any edge that still improves. If one does, then some walk around a loop keeps getting cheaper, and no shortest path exists. Here no edge improves, so the answer is no.

Look at the guard dist[e.a] != INF. An unreachable vertex has infinity as its distance. Adding a cost to LLONG_MAX overflows, which is undefined behaviour in C++. The guard skips those edges, so no unreachable vertex is ever used to compute a distance. The mistakes section shows what happens without it.

The variable type is long long because the costs can add up. With a 64-bit type, the sum of thousands of costs fits easily, but with int a long chain of edges could overflow.

Detecting a negative cycle

A negative cycle is a loop whose costs add up to less than zero. Walking around it once makes the cost lower. Walking around it twice makes it lower again. There is no bottom, so no shortest path exists. Any vertex reachable from a negative cycle has no true shortest distance.

Bellman-Ford finds negative cycles with the extra pass. Why exactly n - 1 rounds plus one more? In a graph with no negative cycle, the shortest path from the source to any vertex has at most n - 1 edges, so after n - 1 rounds every distance is final. Another pass cannot improve anything. If a pass still improves a distance, then a path with at least n edges is cheaper than every path with fewer edges, and that is possible only if the path contains a negative cycle.

The second program applies that test to a small graph. It answers only yes or no. The first graph has a loop from vertex 1 to 2 and back, with costs -2 and -1. That loop adds to -3, which is negative, and it is reachable from the source. The second graph is a simple line with no loop.

Type this into the Input box. The loop 1 -> 2 -> 1 has total cost -2 + -1 = -3:

3 3 0
0 1 1
1 2 -2
2 1 -1

The program prints:

negative cycle reachable: yes

Now type a graph with the same vertices and no loop. It is a line 0 -> 1 -> 2:

3 2 0
0 1 1
1 2 -2

The program prints:

negative cycle reachable: no

The first answer is right, and it shows the mechanism. Every round lowers the distances around the loop, so the check still finds an improvement after the rounds are done. The second graph has no loop, so after two rounds nothing changes, and the check finds nothing.

Trace the first graph by hand. The edges, in order, are 0 -> 1 with cost 1, 1 -> 2 with cost -2, and 2 -> 1 with cost -1. The source is 0, and the number of rounds is n - 1 = 2.

Round 1. Edge 0 -> 1: 0 + 1 = 1, so dist[1] = 1. Edge 1 -> 2: 1 - 2 = -1, so dist[2] = -1. Edge 2 -> 1: -1 - 1 = -2, which beats 1, so dist[1] = -2.

Round 2. Edge 0 -> 1: 1 does not beat -2. Edge 1 -> 2: -2 - 2 = -4, which beats -1, so dist[2] = -4. Edge 2 -> 1: -4 - 1 = -5, which beats -2, so dist[1] = -5.

Check pass. Edge 0 -> 1 does not improve. Edge 1 -> 2: -5 - 2 = -7, which beats -4. Something still improves, so the answer is yes.

The numbers show what the loop does. Each lap 1 -> 2 -> 1 costs -2 - 1 = -3, so every lap pushes the distances lower. The program stops after the fixed number of rounds, which is why the distances are not a real answer for this graph. The check is the only result that matters here.

One caveat is important. This program answers whether a negative cycle is reachable from s. A negative cycle in a part of the graph that the source cannot reach does not matter to this check. Many problems ask about reachability from every vertex, and then you add a virtual source with a zero-cost edge to every vertex.

The second worked example: cheapest route with limited stops

Bellman-Ford's rounds have a natural meaning in a route problem. Each round allows one more edge in a path. That gives a clean solution to a common interview problem: find the cheapest trip from src to dst that uses at most k stops. A trip with k stops uses at most k + 1 flights.

The usual approach uses Dijkstra with an extra counter. That is correct, but a simpler method uses the rounds. Run exactly k + 1 rounds. In each round, compute the new distances from the previous round's values only, not from values already updated in this round. That restriction is what keeps the number of flights counted correctly. After k + 1 rounds, the value at dst is the cheapest trip with at most k stops.

Here is a worked example. The flights are 0 -> 1 (100), 1 -> 2 (100), 2 -> 0 (100), 1 -> 3 (600) and 2 -> 3 (200). The trip from 0 to 3 with one stop can use two flights. The cheapest such trip is 0 -> 1 -> 3, which costs 100 + 600 = 700. With two stops, three flights are allowed, and the trip 0 -> 1 -> 2 -> 3 costs 100 + 100 + 200 = 400, which is cheaper.

The program below runs k + 1 rounds. It copies the distances at the start of each round, so each round reads from the previous round only.

Type this into the Input box. The first line is n m, then the five flights, then src dst k. This example allows one stop:

4 5
0 1 100
1 2 100
2 0 100
1 3 600
2 3 200
0 3 1

The program prints:

700

Change the last line to allow two stops by typing 0 3 2. The program prints:

400

Trace the first answer. Before any round, only src has a cost, which is 0. The first round lets one flight be used. From 0, the flight to 1 costs 100, so dist[1] = 100. The second round lets two flights be used. From 1, the flight to 3 costs 600, so dist[3] becomes 100 + 600 = 700. The flight from 1 to 2 makes dist[2] = 200. Since k = 1 needs k + 1 = 2 rounds, the answer is 700.

For k = 2, one more round is allowed. In the third round, the flight from 2 to 3 costs 200, and dist[2] was already 200 after the second round. So dist[3] becomes 200 + 200 = 400, which beats 700. The answer is 400.

The table below shows the state of dist at the start and after each pass, for the same four-city example. INF stands for unreached.

With k = 1 the program makes two passes, so the answer is the value after pass 2, which is 700. With k = 2 it makes three passes, and the answer is the value after pass 3, which is 400. Read the table column by column. The 700 route appears in pass 2, because it uses two flights. The 400 route appears in pass 3, because it uses three flights. A route that needs more flights than the passes allow simply has not appeared yet.

The key line is the copy vector<long long> next = dist;. Without it, a flight updated earlier in the same round could be used by a later flight in the same round, and that would allow more flights than the round count. With the copy, the round counts flights exactly.

This is the second place where the rounds matter. The number of rounds is a limit on the number of edges, which is the same idea as the n - 1 limit in the general case. The values after each round form a dynamic programming table, and the animation below fills one in.

Watch the values fall as the rounds go on. A value only drops when a round finds a cheaper trip with one more flight allowed. The final value is the answer for the largest k you have.

The third program: early stopping and the number of rounds

Bellman-Ford does not always need all n - 1 rounds. If a round changes nothing, every distance is final, and later rounds cannot help. Stopping early is a useful speed-up on graphs where the shortest paths are short. The fourth program stops as soon as a round changes nothing, and it reports how many rounds it used.

Type the same ten-edge graph from the first program into the Input box. The program prints:

rounds used: 3
dist[0] = 0
dist[1] = 2
dist[2] = 7
dist[3] = 4
dist[4] = -2

The distances are the same as before. The round count is 3, not 4. Round 1 and round 2 both changed something. Round 3 went through every edge and changed nothing, so the loop stopped. The round that changes nothing is counted, because the program only learns it changed nothing by running it. A common question is why the count is 3 and not 2. The answer is that the check needs a round to confirm.

The early stop is a worthwhile speed-up in practice. In the worst case it saves nothing, so keep the n - 1 limit in the loop condition. It is the bound that makes the algorithm correct on a graph where the changes keep going.

Choosing an algorithm

Every graph problem in this module comes down to a few standard tools. The table below is the one to memorise. Read it from the top, and check the condition in the second column against the problem before you pick the row.

To apply the table, ask three questions. Does the problem count edges or costs? If costs, are any negative? Does the problem need a path, an order, a tree or a group? The answers select the row.

Two combinations are worth noting. If a problem seems to need shortest paths with negative edges and also asks for the cheapest route with few stops, Bellman-Ford with rounds is the usual answer. If a problem asks for the cheapest route on a graph where every edge is the same cost, use BFS, because it is faster and simpler than Dijkstra.

What happens inside the loops

Bellman-Ford's inner loop reads one edge and at most writes one distance. Each round reads all e edges, so one round costs O(e). Over n - 1 rounds, the total is O(n * e). The memory is O(n) for the distances and O(e) for the edge list. The vectors are the only big allocation, and the copy in the flights program costs O(n) per round.

Dijkstra and Bellman-Ford solve overlapping problems, so the difference is worth stating in plain words. Dijkstra finishes each vertex once, in the order of cost, and each edge is looked at once. Bellman-Ford does not finish vertices. It rescans every edge in every round, and it trusts the round count to make the answer right. The price of the flexibility is a much bigger number of steps. For a graph with a million edges and a thousand vertices, the difference between n * e and (n + e) log n is roughly a hundred times.

Common mistakes

The first mistake is adding to infinity. If dist[v] is LLONG_MAX for an unreached vertex, the expression dist[v] + w overflows when w is positive, which is undefined behaviour in C++. Even when w is negative, the sum is no longer infinity, so an unreached vertex looks reached. The fix is the guard used in the programs: check dist[a] != INF before you add.

To see the damage, run the same check without the guard. A tiny graph has one edge 1 -> 2 with cost -2, and vertex 1 cannot be reached from the source 0. The program then gives vertex 1 no real distance and vertex 2 the fake distance 9223372036854775805, which looks like a real cost. The output is:

0 -1 9223372036854775805 
no

Here -1 stands for "no value", which the program printed by hand. The number in the third slot is a wrong answer that looks right.

The second mistake is running only n - 2 rounds, or checking for a negative cycle too early. A shortest path with no cycle can have n - 1 edges. If you stop one round early, you can miss the last edge of that path, and the answer is wrong. Check the loop bound against that path length.

The third mistake is treating an undirected negative edge as fine. If the edge a - b has a negative cost and the graph is undirected, you can walk a -> b -> a -> b forever, and each lap lowers the cost by twice the edge's cost. An undirected negative edge is therefore itself a negative cycle. Bellman-Ford will report it, and you should treat it as a special case in the problem.

The fourth mistake is reaching for Dijkstra when one cost is negative. The proof of Dijkstra fails, and the answer can be wrong, as the previous lesson showed. Check every cost in the input before you pick the algorithm.

The fifth mistake is forgetting the copy in the round-limited version. Without next, a flight updated earlier in the same round can be used later in the same round, which lets the path use more flights than the round count allows. The answer then drops below what the problem permits.

A debugging walkthrough

A classmate's negative-cycle program reports yes on a graph that has no cycle at all. The graph is a line from 0 to 3, with some negative costs. What do you do?

Run the program with a tiny input, a line of three vertices, and print the distances after every round. Add a cerr line after each round that prints the whole distance array. A correct run on a line settles after two rounds, and the check finds nothing. If the distances keep changing after round 2, the bug is in the update.

Next look at the update line. A common error is dist[e.b] = dist[e.a] + e.w without the guard on dist[e.a]. In that case an unreached vertex with a negative edge looks reached, and its fake value keeps getting lowered, so the check keeps finding improvements. The fix is the guard. Run the line-shaped graph again. The answer should now be no.

If the update is right, check the loop bounds. A check that uses n rounds instead of n - 1 can still work, but a check that runs the wrong edge list, or updates the distances while it is checking, will report a cycle on a valid graph. Keep the check read-only: it must test each edge without changing anything.

Patterns that come up in interviews

Bellman-Ford appears in problems about currency arbitrage, where a loop of exchanges that multiplies to more than 1 is the same as a negative cycle after taking logarithms. It also appears in "cheapest flight with at most k stops", as in the second program here. When you see a stop limit or an edge-count limit, think of rounds.

Another use is in scheduling with minimum gaps. A rule such as "task b must start at least 3 days after task a starts" becomes an edge with a cost of -3. Bellman-Ford then decides whether all the rules can be met at once. If the rules form a negative cycle, they contradict each other, and no schedule exists.

The choosing table is the thing to bring to an interview. An interviewer who asks you to compare BFS, Dijkstra and Bellman-Ford wants three things. The first is the condition under which each one is correct. The second is the running time. The third is what goes wrong when the condition fails. You now have all three.

Finally, remember that many interview graph problems are a disguise for one of these eight rows. Name the row before you write the code. Once the row is right, the code is usually the standard loop with a small change.

Practice

1. Change edge 3 -> 1 to weight -9 in the first program and run it. What does the negative-cycle check say, and why?

2. Modify the early-stop program so that it also prints the round number in which each vertex's distance last changed. Hint: keep a vector<int> last(n, 0) and set last[e.b] = round when you update.

3. Pick the algorithm for this problem: a shortest flight route with prices that are all positive, from one city to another. Hint: check the row of the table for costs that are at least 0.

4. Explain why the k-stops program copies dist into next each round. Hint: imagine a flight from 0 to 1 and a flight from 1 to 3 both in the same round, with the flight list in that order.

5. Write a function that reports whether a negative cycle is reachable from any vertex, not only from the source. Hint: add a new source vertex with a zero-cost edge to every vertex, then run the check once.

6. A currency exchange has rates. Each conversion multiplies your money by a rate. Explain how a profitable loop of conversions relates to a negative cycle after taking the negative logarithm of each rate. Hint: the logarithm turns multiplication into addition, and a product above 1 becomes a sum below 0.

7. Show that a shortest path with no cycle has at most n - 1 edges. Hint: a path with n edges visits n + 1 vertex positions, so some vertex appears twice, which means the path has a cycle.

8. Explain in plain words why an undirected graph with a negative edge always has a negative cycle. Hint: walk the edge forwards and back.

9. Write a route program that finds the cheapest route with exactly k stops, not at most k. Hint: track the cost of routes with exactly j flights for each j, and take the value at k + 1 flights.

10. Use the choosing table to decide the algorithm for these three problems: (a) the time for a signal to reach every node in a network with positive delays, (b) the order to take university courses with prerequisites, (c) the cheapest set of roads that keeps all towns connected.

What you now know

• Bellman-Ford relaxes every edge in every round. After n - 1 rounds every shortest path with no cycle is final.
• It handles negative edges. A further round that still improves a distance means a negative cycle is reachable.
• Guard every addition against unreached vertices. Adding to infinity overflows or looks reached.
• A limit of k + 1 rounds, with a copy of the distances, finds the cheapest route with at most k stops.
• Dijkstra is faster but needs non-negative costs. Bellman-Ford is slower but works with negative costs.
• Choose an algorithm by three questions: counting edges or costs, whether any cost is negative, and whether the answer is a path, an order, a tree or a group.
• Bellman-Ford runs in O(n * e) time and O(n + e) memory.