Consider the following shortest$-$route problem involving seven cities. The distances between the cities are given below.

Path Distance

$1$ to $25$

$1$ to $39$

$1$ to $48$

$2$ to $35$

$2$ to $56$

$3$ to $44$

$3$ to $52$

$3$ to $65$

$4$ to $69$

$5$ to $78$

$6$ to $76$

Draw the network for this problem.

A graph with $7$ nodes and $11$ arcs is shown.

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

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

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

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

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

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

A graph with $7$ nodes and $11$ arcs is shown.

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

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

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

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

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

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

A graph with $7$ nodes and $11$ arcs is shown.

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

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

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

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

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

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

A graph with $7$ nodes and $11$ arcs is shown.

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

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

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

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

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

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

Formulate the LP for finding the shortest distance from City $1$ to City $7.($Let xij represent the flow from node i to node j$.)($I need answrs in min and all the node flows with the right formatting$)$

Min

s$.$t$.$

Node $1$ Flows

Node $2$ Flows

Node $3$ Flows

Node $4$ Flows

Node $5$ Flows

Node $6$ Flows

Node $7$ Flows

xij $>0$ for all i and j