Suppose a road network in the form of a graph G(V, E, l), which connects a set of cities V . We assume that the network is directed and that every...

Suppose a road network in the form of a graph G(V, E, l), which connects a set of cities V . We assume that the network is directed and that every road (u, v) ∈ E has a non-negative length l(u, v). A new road is about to be constructed, so there is a list E 0 containing pairs of cities that it could connect. Every pair (u, v) ∈ E 0 has a corresponding length l 0 (u, v). We want to choose the pair of cities that succeeds the maximum reduction in distance between two cities s, t ∈ V . Write an efficient algorithm for this problem. Explain thoroughly the correctness and complexity of your algorithm.