🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Shortest Paths: all 10 questions

Quiz: Shortest Paths · Question 4 of 10

In the heap version of Dijkstra, why do we skip a popped pair when d dist[u]?

In the heap version of Dijkstra, why do we skip a popped pair when d > dist[u]?

  1. A.To detect negative cycles
  2. B.Because that node is the source
  3. C.It is an old entry; a shorter distance to u was already found and processed
  4. D.Because the heap is full
Answer & explanation

Correct answer: It is an old entry; a shorter distance to u was already found and processed

We push a new pair instead of updating the old one, so outdated pairs must be ignored when popped.

Can you get the rest right without peeking?

Take the timed Quiz: Shortest Paths quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →