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.

Settle the closest node

Test your knowledge

What happens if edge weights are negative?

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?