Practice question · Multiple choice
Dijkstra's shortest-path algorithm is greedy and provably optimal, until an edge has negative weight, when it breaks. What assumption did the proof rely on?
Hints
- Dijkstra finalises a node and never revisits it. Ask what justifies that.
- Could a longer route through a negative edge end up cheaper?
Show the answer
B. That extending a path never makes it shorter
Why
The greedy step is safe only because distances never decrease as paths grow, so the nearest unvisited node cannot be improved later. A negative edge breaks that guarantee and the finalisation becomes premature, which is why Bellman-Ford, slower and relaxing repeatedly, exists for those graphs.
Practise Greedy Choices and Counterexamples
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Greedy Choices and Counterexamples
- Select every true statement about greedy algorithms.
- Greedy change-making with British coins always gives the fewest coins, and with the coin set {1, 15, 20} it…
- Order what happens when greedy makes change for 30 with coins {1, 15, 20}.
- Sort each problem by whether the greedy approach is provably optimal or can fail.