The 'relax' operation on edge (u, v) with weight w updates d[v] when
Ad[u] + w < d[v]; path via u is shorter than current best
Bv has not been visited yet, regardless of distance
Cu is the source vertex
Dthe edge has the smallest weight in the graph
Answer & Solution
Correct answer: A. d[u] + w < d[v]; path via u is shorter than current best
Relaxation: if reaching v via u (distance d[u] + w) is shorter than the current best d[v], update d[v] = d[u] + w. This is the only update step; otherwise leave d[v] alone. The 'visited yet' or 'is source' or 'smallest weight' tests are unrelated to relaxation logic.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for