Consider the following shortest$-$route problem involving six cities with the distances given.

$\backslash$table$[[$Path$,$Distance$],[1$ to $2,2],[1$ to $3,2],[2$ to $4,5],[2$ to $5,6],[3$ to $4,4],[3$ to $5,8],[4$ to $6,7],[5$ to $6,2]]$

Draw the network for this problem.

$\%$

webassign.net$/$web$/$Student$/$Assignment$-$Responses$/$submit$?$dep$=33506068$&tags$=$autosave#question$4537045\_2$

$($i$)0$

Formulate the LP for finding the shortest distance from City $1$ to City $6.($Let $x_{ij}$ represent the flow from node $i$ to node $j.)$

Min

s$.$t$.$

Node $1$ Flows

Node $2$ Flows

Node $3$ Flows

Node $4$ Flows

Node $5$ Flows

Node $6$ Flows

$x_{ij}>0$ for all i and $j$