← 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]?
- A.To detect negative cycles
- B.Because that node is the source
- C.It is an old entry; a shorter distance to u was already found and processed
- 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 →