A developer uses Dijkstra's algorithm on a graph with mostly positive edge weights but a few negative ones. The algorithm sometimes returns incorrect shortest paths. What is the root cause?
ADijkstra's algorithm cannot handle directed edges, only undirected graphs
BDijkstra's greedy assumption — that once a node is finalized its shortest distance is permanent — breaks when negative weights allow a later-discovered path to improve an already-finalized distance
CDijkstra's priority queue cannot store negative distance values
DDijkstra requires exactly V-1 iterations; fewer edges in the path than V-1 causes it to terminate too early
Dijkstra's correctness relies on the guarantee that the shortest path to a node already processed will never improve. With all non-negative weights, this holds — a later path through unexplored nodes can only be longer. With negative weights, a path through an unvisited node might subtract enough weight to beat the already-finalized distance, invalidating the greedy approach entirely. Bellman-Ford avoids this by never finalizing distances — it keeps relaxing.
Question 2 Multiple Choice
After running V-1 iterations of Bellman-Ford, you run one additional relaxation pass over all edges and find that the distance to node X decreases. What does this tell you?
AThe algorithm needed more iterations; V-1 was insufficient for this graph
BThe graph contains a negative-weight cycle reachable from the source — shortest paths in such graphs are undefined because you could loop around the cycle to reduce distance indefinitely
CThe edge weights were incorrectly specified and should be rechecked
DThe algorithm converged correctly; the decrease is due to floating-point rounding error
After V-1 iterations, all true shortest paths (assuming no negative cycles) have been found — because no simple path visits more than V-1 edges. If a distance still decreases in iteration V, it means some cycle with negative total weight is reachable and is being traversed, causing the distance to decrease without bound. This is Bellman-Ford's negative cycle detection mechanism, which Dijkstra lacks entirely.
Question 3 True / False
Bellman-Ford requires exactly V-1 iterations because any shortest path in a graph without negative cycles uses at most V-1 edges.
TTrue
FFalse
Answer: True
A simple path (one that doesn't revisit vertices) through a graph with V vertices visits at most V vertices, therefore uses at most V-1 edges. After k iterations of Bellman-Ford, all shortest paths that use at most k edges are correctly computed. So after V-1 iterations, the longest possible simple shortest path has been discovered. This bound is tight — a linear chain of V nodes has a shortest path of exactly V-1 edges.
Question 4 True / False
Bellman-Ford can correctly report shortest-path distances in graphs with negative-weight cycles by flagging the affected nodes.
TTrue
FFalse
Answer: False
When a negative-weight cycle is reachable from the source, shortest paths to nodes reachable via that cycle are undefined — you can keep traversing the cycle to reduce the distance without bound, so no finite minimum exists. Bellman-Ford detects that a negative cycle is present (by showing that distances continue to decrease after V-1 iterations) but cannot produce valid distance values for affected nodes. The algorithm reports the existence of a negative cycle; it does not produce meaningful distances.
Question 5 Short Answer
Why does Bellman-Ford require exactly V-1 iterations, and what property of shortest paths justifies this bound?
Think about your answer, then reveal below.
Model answer: Any shortest path in a graph without negative cycles is a simple path — it visits no vertex more than once (since revisiting a vertex with non-negative-weight cycles could only increase cost). A simple path through V vertices uses at most V-1 edges. After the kth Bellman-Ford iteration, all shortest paths using at most k edges are correct. Therefore V-1 iterations suffice to find all shortest paths, however long.
The V-1 bound is both an upper bound (no more is needed) and a tight bound (a linear chain of V nodes requires exactly V-1 iterations). This contrasts with Dijkstra, which processes each node once but requires non-negative weights. Bellman-Ford's patient, redundant approach is what lets it handle negative weights correctly.