Graduate base, proof. Description:

Gives a proof if the answer is yes or a no.

We would need an arc that goes over $O(n^2)$ many pairs of paths for all the possible path, and we need to firstly show that the previous algorithm 5.40 is not going to work anymore and, if would have no choice to look over almost all the possible path to figure out the optimal path for the pertrubed costs!