CO$2$ a$)$ Simulate Dijkstra's algorithm to find the weight of the shortest path from $G$ to $B.$

b$)$ There is a proposal to add one new road to this network, and there is a list of five pairs of

cities between which the new road can be built. Each such potential road has an associated

length. As a designer for the public works department, you are asked to determine the road

whose addition to the existing network would result in the maximum decrease in the

distance from $G$ to $B.$ One way to do this would be to add each of the five edges separately,

run Dijkstra's algorithm five different times, and then compare the results. But can you do

this by invoking Dijkstra's algorithm only two times $($and possibly doing a linear amount of

extra work$)?$

Present your idea with a pseudo$-$code$/$flowchart$/$step by step instruction$/$algorithm$.$ handwritten ans only