Questions: Dijkstra's Algorithm

Question 1

Why does Dijkstra's algorithm produce incorrect results when the graph contains a negative edge weight?

• A. The priority queue cannot store negative numbers.
• B. The algorithm may finalize a node's distance as shortest, but a later negative edge could provide an even shorter path to that node.
• C. Negative weights cause the algorithm to run forever in an infinite loop.
• D. The algorithm only works on trees, not graphs with cycles.

Answer: (B)

Dijkstra's correctness relies on a key invariant: once a node is extracted from the priority queue (finalized), its tentative distance is already the true shortest distance and will never decrease. With non-negative weights, every subsequent path through an unvisited node can only be longer. A single negative edge breaks this: a finalized node could later be reached via a cheaper path using that negative edge, but the algorithm has already moved on.

Question 2

Dijkstra's algorithm with a binary heap priority queue runs in O(V²) time.

• T. True
• F. False

Answer: False

With a binary heap, Dijkstra's runs in O((V + E) log V) — each of the V node extractions and up to E edge relaxations costs O(log V) for the heap operation. O(V²) is the complexity of the naive array-based implementation where finding the minimum-distance unvisited node requires scanning all V nodes each time. The binary heap version is strictly better for sparse graphs where E << V².

Question 3

How does Dijkstra's algorithm differ from BFS, and when would you choose one over the other?

Model answer: BFS finds shortest paths in unweighted graphs (or graphs where all edges have equal weight) by exploring nodes layer by layer. Dijkstra's generalizes this to weighted graphs by using a priority queue keyed on cumulative path cost rather than hop count. Use BFS when edges are unweighted or all equal — it is simpler and O(V + E). Use Dijkstra's when edge weights differ and are non-negative.

BFS's 'layer' structure is implicitly a priority queue ordered by hop count — each node is processed in the order it was first discovered, which corresponds to fewest edges. Dijkstra's replaces 'fewest edges' with 'minimum total weight' by swapping the queue for a min-heap. The algorithmic structure is nearly identical; only the ordering changes. This connection to BFS — which is a prerequisite — makes Dijkstra's feel like a natural extension rather than a new algorithm.