Questions: Dijkstra's Shortest Path Algorithm

Question 1

You run Dijkstra's algorithm on a graph that contains one edge with weight -3. What is the risk?

• A. The algorithm crashes because priority queues cannot store negative keys
• B. The algorithm runs correctly but is slower than usual
• C. The algorithm may return incorrect shortest paths because settling a node is no longer guaranteed to be final
• D. The algorithm works as long as the negative edge is not on the shortest path

Answer: (C)

Dijkstra's correctness rests on the greedy guarantee: once a node is pulled from the priority queue, its recorded distance is final. This holds only because all edge weights are non-negative — no future path can be cheaper than the one already settled. A negative edge breaks this: a later path through a negative-weight edge could undercut an already-finalized distance. The algorithm won't crash, but it may report a non-optimal path. Bellman-Ford handles negative weights correctly.

Question 2

Why does Dijkstra's algorithm use a priority queue (min-heap) instead of the regular FIFO queue used in BFS?

• A. A priority queue is required to handle graphs with cycles; a FIFO queue would loop infinitely
• B. BFS visits all neighbors at once, which doesn't work for weighted graphs; the priority queue ensures we always extend the cheapest known path next
• C. Priority queues are faster than FIFO queues for all graph traversal tasks
• D. The FIFO queue cannot store weighted edges, so a priority queue is used as a workaround

Answer: (B)

BFS works for unweighted graphs because every edge costs 1 — the first time you reach a node is the cheapest route. With unequal weights, the first-found path is not guaranteed to be cheapest. The priority queue ensures that among all currently-known paths, we always extend the one with the smallest total cost so far. This is the greedy insight: committing to the cheapest frontier node is always safe when weights are non-negative.

Question 3

Dijkstra's algorithm may return incorrect shortest paths if any edge in the graph has a negative weight.

• T. True
• F. False

Answer: True

The correctness proof depends entirely on the invariant that once a node is settled (pulled from the priority queue), its distance is final. With non-negative weights, this holds because adding more edges can only increase total cost. A negative edge breaks the invariant: a path through that edge might later be discovered to be cheaper than what was already settled. The algorithm produces wrong answers in such cases — not a crash, just incorrect output.

Question 4

Dijkstra's algorithm visits nodes in the order they were first discovered, just like BFS.

• T. True
• F. False

Answer: False

BFS visits nodes in discovery order (FIFO). Dijkstra visits nodes in order of their current best-known distance from the source. A node discovered early might have a large initial estimate and be visited late; a node discovered later might jump to the front of the priority queue because it has a very low total cost path. This is the fundamental difference: Dijkstra is driven by cost, not by discovery order.

Question 5

Explain the greedy guarantee behind Dijkstra's correctness: why is it safe to permanently finalize a node's shortest distance when it is extracted from the priority queue?

Model answer: When a node is pulled from the priority queue, it has the smallest current distance among all unvisited nodes. Any alternative path to that node would have to go through other unvisited nodes first — but those nodes all have equal or greater distance. Since edge weights are non-negative, adding more edges can only increase or maintain the total cost, never decrease it. Therefore, no future path can be cheaper than the one already recorded. The finalization is safe precisely because costs cannot decrease as you extend a path.

This greedy guarantee is what makes Dijkstra efficient and correct simultaneously. It allows us to 'close' each node permanently in one pass rather than revisiting it. The non-negative weight requirement is not an arbitrary restriction — it is exactly the condition that makes the guarantee valid. Negative edges allow future paths to be cheaper than settled ones, which is why Bellman-Ford (which doesn't finalize nodes permanently) is needed for those cases.