← All topics
Quiz: Shortest Paths: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. What does "relaxing" the edge u → v with weight w mean?
- Q2. What does this print? (code)
- Q3. Why can't Dijkstra's algorithm handle negative edge weights?
- Q4. In the heap version of Dijkstra, why do we skip a popped pair when d dist[u]?
- Q5. How many rounds of "relax every edge" does Bellman-Ford need for V nodes (without the check round)?
- Q6. After V − 1 rounds of Bellman-Ford, one more round still lowers a distance. What does that tell you?
- Q7. What does this print? (code)
- Q8. In 0-1 BFS, after relaxing an edge of weight 0 to node v, where is v pushed?
- Q9. A city map has non-negative travel times on 10⁵ roads. Which algorithm fits best?
- Q10. What is the time complexity of Bellman-Ford?