If Bellman-Ford performs a V-th iteration and STILL relaxes some edge, the algorithm concludes that
Aa negative-weight cycle is reachable from the source
Bthe graph is sparse and needs Dijkstra instead
Cthe source vertex is disconnected
Dthe priority queue is exhausted
Answer & Solution
Correct answer: A. a negative-weight cycle is reachable from the source
After V − 1 iterations Bellman-Ford has correctly computed all shortest paths (which use at most V − 1 edges). If a V-th pass still finds an improvable edge, no finite shortest path exists from s to that subgraph — a negative cycle must be reachable. Bellman-Ford uniquely detects this; Dijkstra cannot.
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