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] + w

Ask 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
AlgorithmCostCorrect whenDetects negative cycles
BFSall weights equal—
Dijkstrano negative weightsno
Bellman–Fordany weightsyes

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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms