Why does Bellman-Ford run exactly V − 1 outer iterations on a graph with V vertices?
AV − 1 is the lower bound for any shortest-path algorithm
Bthe priority queue holds V − 1 elements at most
Cany shortest path has at most V − 1 edges, so V − 1 passes suffice
DV − 1 matches the number of edges in a spanning tree
Answer & Solution
Correct answer: C. any shortest path has at most V − 1 edges, so V − 1 passes suffice
A simple shortest path can repeat no vertex, so it has at most V − 1 edges. After k passes of relax-every-edge, all shortest paths of ≤ k edges are correctly computed. By pass V − 1, every reachable vertex has its true shortest distance. A V-th pass that still relaxes means a negative cycle exists.
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