Micro-questions over the Dijkstra module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why it exists

1. What problem does Dijkstra solve?

Answer

Single-source shortest paths in a weighted graph — smallest total weight, not fewest edges.

2. Give the GPS illustration of why BFS is not enough.

Answer

A 1-hop highway (90 minutes) versus a 2-hop route through a village (30 minutes). BFS picks the fewest-hops highway; Dijkstra evaluates total cost and picks the faster two-hop route.

3. State the difference between BFS and Dijkstra in one sentence.

Answer

BFS counts edges with a queue; Dijkstra sums weights with a min-heap.

4. Name three production applications.

Answer

GPS navigation (Google Maps, Waze), network IP routing (OSPF, on latency), and flight booking search for cheapest combinations.


B. The vocabulary

5. What is an edge weight?

Answer

The numeric cost of travelling across an edge — distance, time, fee.

6. What is relaxation?

Answer

Updating the shortest known distance to a node when a cheaper path is discovered. Finding a shortcut road.

7. What does the min-heap do here?

Answer

Always pops the unvisited node with the smallest cumulative distance — i.e. always processes the closest node next.

8. What is a stale entry?

Answer

An outdated (distance, node) pair left in the heap after a shorter path to that node was found. An expired route suggestion.

9. Why do stale entries exist at all?

Answer

Because a binary heap has no cheap “decrease-key”. Instead of updating an entry in place you push a new, better one and let the old one sit there — lazy deletion.


C. The algorithm

10. Give Dijkstra in five steps.

Answer
  1. distances[source] = 0, everything else infinity.
  2. Push (0, source) into a min-heap.
  3. Pop the smallest (dist, node). If dist > distances[node], skip it — stale.
  4. For each neighbour: new_dist = dist + weight.
  5. If new_dist < distances[neighbor], relax and push (new_dist, neighbor).

11. What is the stale check line, exactly?

Answer
if current_dist > distances[current_node]:
    continue

12. Why is the popped node’s distance final?

Answer

Because every remaining route to it must pass through some node still in the heap, whose distance is at least as large — and all weights are non-negative, so it can only grow from there.

13. What is the greedy assumption, stated precisely?

Answer

Once a node is popped from the heap, its distance is final and will never decrease.


D. Negative weights

14. Why does Dijkstra fail on negative edge weights?

Answer

The greedy assumption breaks: a longer path with 10 hops could suddenly become cheaper later if it contains a edge. Dijkstra has already finalised the node and will never revisit it.

15. What do you use instead?

Answer

Bellman-Ford, at .

16. Can you just add a constant to every weight to make them positive?

Answer

No. Adding to every edge penalises paths with more edges by per edge, which changes which path is cheapest. (The correct reweighting is Johnson’s algorithm, which uses Bellman-Ford potentials.)


E. Costs

17. Time complexity, and where each part comes from?

Answer

— every vertex is popped from the heap, and every edge can trigger a push, each costing .

18. Space complexity?

Answer

— the adjacency list plus heap storage.

19. How large can the heap get with lazy deletion?

Answer

Up to entries, since each relaxation pushes one. That is why the bound is often written .


F. Traps

20. What happens if you skip the stale entry check?

Answer

The answers stay correct, but you waste massive CPU re-exploring outdated paths. It is a performance bug, not a correctness bug.

21. Why must you never use Dijkstra with negative edges “just to see”?

Answer

It fails silently — it returns plausible-looking distances that are simply wrong, with no error.

22. Summarise the BFS/Dijkstra distinction in structures and costs.

Answer

BFS: simple queue, , unweighted graphs. Dijkstra: min-heap, , non-negative weighted graphs.

23. When is BFS the right choice even on a weighted graph?

Answer

When all weights are equal — fewest edges then is cheapest, and BFS is strictly faster.

24. Summarise Dijkstra in one sentence.

Answer

Always expand the cheapest-known node next, relax its edges, and trust that non-negative weights make the first arrival final.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms