Problem $4(33$ points$)$

Consider the following directed network.

$($a$)(15$ pts$.)$ Assume that the numbers on the arcs in the network above are distances and use Dijkstra's algorithm to find the shortest path from node A to node G$.$

$($b$)(12$ pts$.)($i$)$ Exxo $76$ is an oil company that operates the pipeline network shown above, and assume each pipeline is labeled with its maximum flow rate in million cubic feet per day. A new oil well has been constructed near A$.$ They would like to transport oil from the well near A to their refinery at G$.$ Formulate and solve a network optimization model to determine the maximum flow rate from $A$ to $G.$

$(3$ pts$.)($ii$)$ Find the optimal flow through each arc.

$(3$ pts$)($iii$)$ Find a cut $($e$.$g$.$ a set of arcs$)$ with total capacity equal to the maximum flow.