Question $1$: Shortest path deeper cuts

$($a$)$ Consider the following statements and answer whether they are true or false. Justify your

answer by providing a proof to the statement $($if true$)$ or by showing a counter example $($when

false$).$

Statement $1.$ A network where all arc costs are different has a unique shortest path

connecting two nodes.

Statement $2.$ In a directed network, if we drop all directions $($that is$,$ every arc can be

traversed in every direction no matter its original sense$),$ the shortest path will not change.

Statement $3.$ Assume we solved the shortest path problem but we underestimated each

arc cost by $k>0$ units $($that is$,$ instead of $c_{ij}$ we should have used hat$(c{)}_{ij}=c_{ij}+k.$ Then,

the solution to the two problems should be the same.

Statement $4.$ Assume we solved the shortest path problem but we underestimated each

arc cost by a factor of $k>0($that is$,$ instead of $c_{ij}$ we should have used hat$(c{)}_{ij}=c_{ij}*k).$

Then, the solution to the two problems should be the same.

$($b$)$ In some instances, we may be interested in finding two shortest paths. Why? Well, in

cases where we are focused on the robustness of the proposed solution, we may want to focus

on having a "Plan B$".$ Specifically, assume that we are interested in solving the $2-$disjointed

shortest paths problem for the same source and terminal nodes. We call two paths disjointed

if they share no arcs $($they are allowed to share nodes, though$).$

An algorithm to tackle this problem is the ingenious Suurballe's algorithm. A big$-$picture

description is offered here:

Compute a shortest path tree from the source $s$ to every other node $($including the terminal

$t.$ Let $d_{si}$ be the distance from $s$ to $i$ in the shortest path tree.

Modify all arc costs to be $c_{ij}^{\text{'}}=c_{ij}+d_{si}-d_{sj}.$ Note how this modification turns all arcs

that are in the shortest path tree to have a cost of $0.$

Construct a residual network by reversing all arcs in the current shortest path from $s$ to

$t$ as well as removing all arcs that are opposite to the shortest path from $s$ to $t($in the

reverse direction than the shortest path from $s$ to $t).$

Find a shortest path from $s$ to $t$ in the residual network.

Discard any arc that appears in both shortest paths in opposite directions. The remaining

arcs form two paths from $s$ to $t$ that share no arcs.

Implement this algorithm using networkx and then solve the network in the Sioux Falls bench$-$

mark $($see the SiouxFalls.txt file that includes the edges and their cost$).$