🎙 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 1 of 10

What does "relaxing" the edge u → v with weight w mean?

What does "relaxing" the edge u → v with weight w mean?

  1. A.Removing the edge from the graph
  2. B.If dist[u] + w is smaller than dist[v], updating dist[v] to dist[u] + w
  3. C.Setting the weight of the edge to 0
  4. D.Marking v as visited
Answer & explanation

Correct answer: If dist[u] + w is smaller than dist[v], updating dist[v] to dist[u] + w

Relaxation is the single update step that every shortest-path algorithm repeats.

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 →