Question $3.(15$ marks$)$ We are given a directed graph $G=(V,E),$ nodes $s,$tinV, and an edge weight

function wt such that $wt(e)0$ for every einE. In addition, we are given a set $E^{\text{'}}$ of potential edges,

i$.$e$.,$ pairs of nodes that are not edges in $E$; and for each $e^{\text{'}}in{E}^{\text{'}}$ we are given a non$-$negative weight $wt(e^{\text{'}}).$

We want to choose a single potential edge in $E^{\text{'}}$ that, if added to the graph, reduces as much as possible

the weight of a shortest $st$ path. $($If there is no potential edge whose addition to $G$ reduces the weight

of the shortest $st$ path, we can choose any potential edge.$)$

Describe an algorithm that solves this problem in $O(k+(m+n)logn)$ time, where $n=|V|,m=|E|,$

and $k=|E^{\text{'}}|.$ Assume that the graph is given in adjacency list form, and the set of potential edges $($and

their associated weights$)$ is given as a list. Your algorithm must be by reduction of the given problem to

the shortest$-$path problem, and using Dijkstra's algorithm to solve that. ${?}^1$ Justify the correctness of your

algorithm and analyze its running time.