Dijkstra's Algorithm

Question 1

What happens if edge weights are negative?

Accepted Answer

It may give an incorrect result — Dijkstra's algorithm assumes non-negative weights. If negative weights exist, Bellman-Ford should be used.

Question 2

Dijkstra's algorithm finds…

Accepted Answer

Shortest paths, non-negative — It computes the shortest distance from one source to every other vertex, provided no edge weight is negative.

Question 3

Why does Dijkstra's algorithm FAIL with negative edge weights?

Accepted Answer

A negative edge can undercut a settled distance — The greedy choice assumes distances only grow; a negative edge can reduce a 'finalized' distance, violating that assumption. Use Bellman-Ford for negatives.

Question 4

With a binary-heap priority queue, Dijkstra's complexity is…

Accepted Answer

O((V + E) log V), heap-based — Each edge can trigger a decrease-key/push (O(log V)) and each vertex is extracted once, giving O((V+E) log V).

Question 5

The core step where Dijkstra updates a neighbor's tentative distance is called…

Accepted Answer

Relaxation — Relaxing edge (u,v) checks whether going through u yields a shorter path to v and updates dist[v] if so.

Question 6

Dijkstra repeatedly selects which vertex to finalize next?

Accepted Answer

The unsettled, smallest dist — The greedy choice extracts the closest unfinalized vertex (via the priority queue); its distance is then provably final.

Question 7

For a DENSE graph (E ≈ V²), a simple array-based Dijkstra runs in…

Accepted Answer

O(V²), can beat the heap — Scanning for the min each step is O(V) over V iterations = O(V²); for dense graphs this matches or beats O(E log V)=O(V² log V).

Question 8

Dijkstra generalizes BFS to weighted graphs by replacing the queue with a…

Accepted Answer

A priority queue — BFS's FIFO queue assumes equal weights; Dijkstra uses a priority queue to always expand the nearest frontier node under arbitrary non-negative weights.

Question 9

The 'lazy deletion' trick in heap-based Dijkstra means…

Accepted Answer

Allowing stale entries in the heap — Instead of decrease-key, you push updated entries and ignore any popped entry whose distance is worse than the recorded one — simpler and often as fast.

Question 10

Dijkstra's correctness relies on which property?

Accepted Answer

Optimal substructure of paths — Because subpaths of shortest paths are optimal and weights are non-negative, finalizing the closest vertex can never be improved later.

Dijkstra's Algorithm

Priority Queue (Min-Heap)

Settle the closest node

Test your knowledge

What happens if edge weights are negative?

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?