solveConsider the graph in Figure $1,$ write down the explicit flow formulation for the single

source shortest path problem using the source node $v_1$ and the target node $v_4,$ and $c_a$ as

the cost of traversing an arc. Solve the problem and write down the solution.

Figure $1$: Arbitary graph.

The flow conservation model for the single source shorest path problem can be solved as a

linear program, explain why and when this is the case.