Micro-questions over the Bellman–Ford module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The wrong answer that looks right
1. State Dijkstra’s correctness assumption precisely.
Answer
Once the closest unfinalised vertex is popped, its distance is final — because every other route would go through a vertex already further away, and extending a path can only make it longer.
2. Which clause is the assumption, and when is it true?
Answer
“Extending a path can only make it longer” — true exactly when every edge weight is non-negative.
3. Trace the smallest graph that breaks Dijkstra: S→A=1, S→B=5, A→C=2, B→C=-4.
Answer
Pop S (0): A=1, B=5. Pop A (1): C=3. Pop C (3) — finalised at 3. Pop B (5): relax C to , better — but C is finalised, so it is discarded.
4. What does Dijkstra report, and what is the truth?
Answer
Dijkstra reports ; the truth is via .
5. Why does this lesson exist at all?
Answer
No exception is raised and no warning is printed. You get a number that is 200% of the truth, and in production you would never know. Not because negative weights are common — because the failure is silent.
B. Where negative weights come from
6. Currency arbitrage — how does it become a graph problem?
Answer
Take as the edge weight. A profitable trading cycle becomes a negative cycle, so finding arbitrage is negative-cycle detection.
7. Give a mundane source of negative weights.
Answer
Any cost that can be a rebate: toll roads with credits, energy recovered on a downhill leg, a delivery route that picks up a paying load partway.
8. What are difference constraints?
Answer
Systems of inequalities , which map directly onto a shortest-path problem with arbitrary-sign weights. It is how schedulers solve timing constraints.
9. Where does Bellman–Ford appear inside another algorithm?
Answer
Johnson’s algorithm — it reweights a graph to remove negative edges so Dijkstra can be run many times, and uses Bellman–Ford once to compute the reweighting.
C. The vocabulary
10. What is relaxation, in code?
Answer
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wAsk whether going via u beats the best route to v found so far; if so, record it.
11. What is a round?
Answer
Also a pass or iteration — one sweep in which every edge in the graph is relaxed once, in some order. Bellman–Ford performs of them.
12. What is a negative cycle, and what does it do to the problem?
Answer
A directed cycle whose weights sum to a negative number. You can lower a path’s cost without limit by going round again, so the shortest path does not merely become hard to find — it does not exist.
13. What is a reachable negative cycle, and why does the distinction matter?
Answer
One you can actually get to from the source. A negative cycle in an unreachable part of the graph affects no distance from that source, and a careful implementation reports only reachable ones.
14. What representation does Bellman–Ford want, and why?
Answer
An edge list — a flat list of triples. It never asks “what are the neighbours of ?”, so an adjacency list buys it nothing.
15. What is early termination, and why is it valid?
Answer
Stop once a full round changes nothing. If an entire pass improves no distance, no later pass can either — the inputs to every comparison are unchanged.
16. What is the predecessor array for?
Answer
Recording which vertex each distance came from, so you can recover an actual path rather than only its cost.
D. The algorithm
17. State Bellman–Ford in one sentence.
Answer
Start with every distance at infinity except the source, then relax every edge in the graph, times over.
18. What is conspicuously absent, and why does that matter?
Answer
No priority queue, no visited set, no finalisation — and the absence of finalisation is precisely why it survives negative weights. A distance can improve right up to the last round.
19. What does the dist[u] != INF guard prevent?
Answer
Relaxing out of an unreached vertex. Without it, an unreachable u with a negative outgoing edge invents a finite distance for v. With floats you may get away with it; with a sentinel integer you will not.
20. What is the extra pass after the rounds for?
Answer
Negative-cycle detection: any further improvement means a negative cycle, because after rounds nothing should be improvable.
E. Why exactly rounds
21. State the invariant.
Answer
After rounds, every vertex reachable by a shortest path of at most edges has its final distance.
22. Why can a shortest path use at most edges?
Answer
A path with edges visits vertices, so by pigeonhole it repeats one — it contains a cycle. With no negative cycle, removing that cycle cannot increase the cost, so a simple shortest path always exists, and a simple path uses at most edges.
23. Why does one round extend the guarantee by one edge?
Answer
If the shortest path to is with edges and dist[u] is final after rounds, then round relaxes every edge including , so dist[v] becomes at most dist[u] + w — the shortest-path value. Induction does the rest.
24. What does the argument deliberately not assume?
Answer
The order of edges within a round. That is why the bound is and not smaller — a bad order makes progress one edge at a time.
25. Show the worst case on a 5-vertex chain.
Answer
Relaxing v0→v1→v2→v3→v4 in reverse order advances exactly one vertex per round: after round 1 only v1, after round 2 only v2, and so on. The same graph in a sensible order converges in a single round.
26. So what is actually a statement about?
Answer
A guarantee about the worst edge ordering, not a description of every run — which is why early termination is worth having.
F. Negative cycles
27. Add C → B with weight to the trap graph. What should dist[B] be?
Answer
There is no correct value. costs ; go round twice and save 10. There is no lower bound, so , and every vertex reachable from the cycle inherits the problem.
28. State the honest framing.
Answer
“Shortest path” is undefined here — not expensive, not hard, undefined.
29. What should you do when you detect one?
Answer
Detect and report — never clamp to a finite value. And if the domain allows it (arbitrage), the cycle itself is the answer you wanted.
30. Distinguish a negative edge from a negative cycle.
Answer
Negative edges are fine and Bellman–Ford handles them exactly. Only negative cycles make the problem undefined. A DAG can have every edge negative and still have well-defined shortest paths.
31. Can Bellman–Ford handle negative weights in an undirected graph?
Answer
No — and the question is not about the algorithm. An undirected edge of weight can be traversed back and forth for , , …, so any negative edge in an undirected graph is automatically a negative cycle. Negative weights only make sense on directed graphs.
G. Choosing between the three
32. Complete the table: cost, correctness condition, negative-cycle detection.
Answer
| Algorithm | Cost | Correct when | Detects negative cycles |
|---|---|---|---|
| BFS | all weights equal | — | |
| Dijkstra | no negative weights | no | |
| Bellman–Ford | any weights | yes |
33. What factor are you paying, concretely?
Answer
. On 10,000 vertices and 50,000 edges: Dijkstra ≈ units of work, Bellman–Ford . Milliseconds versus minutes — which is why nobody uses Bellman–Ford when Dijkstra is valid.
34. What is SPFA, and what is the trap in quoting it?
Answer
Bellman–Ford with a queue of vertices whose distance changed, so you only relax edges out of those. Much faster in practice — but the same worst case, with adversarial graphs built specifically to defeat it. Never quote it as an asymptotic improvement.
35. What is the right answer on a DAG?
Answer
Neither. Relax edges in topological order and you get shortest paths in with any weights, negative included — because a topological order guarantees you never need to revisit.
H. Traps
36. Why is “the weights are probably fine, use Dijkstra” the worst pitfall?
Answer
If a weight can be negative, Dijkstra is not a fast approximation — it is an incorrect algorithm that returns a confident number. Check the sign constraint; do not assume it.
37. What do the distances mean if you skip the extra pass?
Answer
Nothing reliable. The extra pass is what distinguishes “these are shortest paths” from “these are how far the algorithm got”.
38. Summarise Bellman–Ford in one sentence.
Answer
Relax every edge times and never finalise anything — slower than Dijkstra by a factor of , and the price of correctness under negative weights plus a cycle detector for free.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Bellman–Ford — the module
- Dijkstra — Question Bank — the algorithm this one repairs
- Floyd–Warshall — Question Bank — all pairs instead of one source
Software engineering
Infrastructure & security
Computer science
Hardware & engineering