Recall the asynchronous version of the Bellman-Ford algorithm discussed in the “Internet Routing” lectures. Prove that, in the worst case, this algorithm requires an exponential number of iterations to converge.

ANSWER: Formal proof TBD. This article has good examples of exponential convergence for the synchronous algorithm.

Updated:

Leave a comment

You may also enjoy