Consider a network in which the N nodes represent locations and the $$cost$$ cij assigned to the

directed arc from node i to node j $($if it exists$)$ is the travel time required to get from i to j by

that arc. $($We assume that all travel times are strictly positive.$)$ Given two particular nodes $($say$,$

node $1$ and node N$),$ we want to find the minimum travel time and an optimal path from node

$1$ to node N$.($We assume it is possible to get from $1$ to N on the given network.$)$ Let$$s show

this can be done by using the simplex method to minimize Pcijxij subject to xij $>=0$ and the

usual network equilibrium constraints, with a unit source at node $1,$ a unit sink at node N$,$ and

no other sources or sinks$.$

$($a$)$ To start, show that if a path from $1$ to N on the network never repeats any node then taking

xij $=1$ on the arcs in the path and xij $=0$ elsewhere gives a feasible point for this LP$.$

Thus the optimal value of the LP is less than or equal to the min travel time. Our task is to

show that it$$s not smaller, and that an optimal x found by the simplex method $($which has

integer entries, by the integrality theorem$)$ is of the type just considered.