Question 18.3: What’s the running time of the Bellman-Ford algorithm, as a ......
What’s the running time of the Bellman-Ford algorithm, as a function of m (the number of edges) and n (the number of vertices)? (Choose the strongest true statement.)
a) O(n²)
b) O(mn)
c) O(n³)
d) O(mn²)
(See Section 18.2.9 for the solution and discussion.)
Correct answer: (b). The Bellman-Ford algorithm solves (n+1) · n = O(n²) different subproblems, where n is the number of vertices. If the algorithm performed only a constant amount of work per subproblem (like in all our previous dynamic programming algorithms aside from OptBST), the running time of the algorithm would also be O(n²). But solving a subproblem for a destination v boils down to computing the recurrence in Corollary 18.2 which, by Quiz 18.2, involves exhaustive search through 1 + in-deg(v) candidates, where in-deg(v) is the number of incoming edges at v.^{16} Because the indegree of a vertex could be as large as n − 1, this would seem to give a running time bound of O(n) per subproblem, for an overall running time bound of O(n³).
We can do better. Zoom in on a fixed iteration of the outer for loop of the algorithm, with some fixed value of i. The total work performed over all iterations of the inner for loop is proportional to
\sum_{v\in V}(1+\mathrm{in-deg} (v))=n+\underbrace{\sum_{v\in V}\mathrm{in-deg}(v)\,}_{=m}.The sum of the in-degrees also goes by a simpler name: m, the number of edges. To see this, imagine removing all the edges from the input graph and adding them back in, one by one. Each new edge adds 1 to the overall edge count, and also adds 1 to the in-degree of exactly one vertex (the head of that edge).
Thus, the total work performed in each of the outer for loop iterations is O(m+n) = O(m).^{17} There are at most n such iterations and O(n) work is performed outside the double for loop, leading to an overall running time bound of O(mn). In sparse graphs, where m is linear or near-linear in n, this time bound is much better than the more naive bound of O(n³).
^{16}Assuming the input graph is represented using adjacency lists (in particular that an array of incoming edges is associated with each vertex), this exhaustive search can be implemented in time linear in 1 + in-deg(v).
^{17}Technically, this assumes that m is at least a constant times n, as would be the case if, for example, every vertex v was reachable from the source vertex s. Do you see how to tweak the algorithm to obtain a per-iteration time bound of O(m) without this assumption?