given.

Path Distance

$1$ to $22$

$1$ to $32$

$2$ to $45$

$2$ to $54$

$3$ to $44$

$3$ to $56$

$4$ to $67$

$5$ to $62$

Draw the network for this problem.

A graph with $6$ nodes and $8$ arcs is shown.

Node $1$ is connected to node $2$ by arc of value $2$ and to node $3$ by arc of value $2.$

Node $2$ is connected to node $4$ by arc of value $5$ and to node $5$ by arc of value $4.$

Node $3$ is connected to node $4$ by arc of value $4$ and to node $5$ by arc of value $6.$

Node $4$ is connected to node $2$ by arc of value $5,$ to node $3$ by arc of value $4,$ and to node $6$ by arc of value $7.$

Node $5$ is connected to node $2$ by arc of value $4,$ to node $3$ by arc of value $6,$ and to node $6$ by arc of value $2.$

A graph with $6$ nodes and $8$ arcs is shown.

Node $1$ is connected to node $2$ by arc of value $2$ and to node $3$ by arc of value $7.$

Node $2$ is connected to node $4$ by arc of value $6$ and to node $5$ by arc of value $4.$

Node $3$ is connected to node $4$ by arc of value $4$ and to node $5$ by arc of value $5.$

Node $4$ is connected to node $2$ by arc of value $6,$ to node $3$ by arc of value $4,$ and to node $6$ by arc of value $2.$

Node $5$ is connected to node $2$ by arc of value $4,$ to node $3$ by arc of value $5,$ and to node $6$ by arc of value $2.$

A graph with $6$ nodes and $8$ arcs is shown.

Node $1$ is connected to node $2$ by arc of value $2,$ to node $3$ by arc of value $2,$ to node $4$ by arc of value $4,$ and to node $5$ by arc of value $4.$

Node $2$ is connected to node $4$ by arc of value $5.$

Node $3$ is connected to node $5$ by arc of value $6.$

Node $4$ is connected to node $2$ by arc of value $5$ and to node $6$ by arc of value $7.$

Node $5$ is connected to node $3$ by arc of value $6$ and to node $6$ by arc of value $2.$

A graph with $6$ nodes and $8$ arcs is shown.

Node $1$ is connected to node $2$ by arc of value $2,$ to node $3$ by arc of value $7,$ to node $4$ by arc of value $4,$ and to node $5$ by arc of value $4.$

Node $2$ is connected to node $4$ by arc of value $6.$

Node $3$ is connected to node $5$ by arc of value $5.$

Node $4$ is connected to node $2$ by arc of value $6$ and to node $6$ by arc of value $2.$

Node $5$ is connected to node $3$ by arc of value $5$ and to node $6$ by arc of value $2.$

Formulate the LP for finding the shortest distance from City $1$ to City $6.($Let xij 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

xij $>0$ for all i and j