### Shortest Path Problem

This problem uses a general network structure where only the arc cost
is relevant. A typical case is shown in Fig. 15. The length of a path is
the sum of the arc costs along the path. The problem is to find the shortest
path from some specified node to some other node or perhaps to all other
nodes. The latter problem is called the shortest path tree problem because
the collection of all shortest paths from a specified node forms a graph
structure called a tree. Since it is not much more difficult to find the
paths to all nodes than it is to find the path to one node, the shortest
path tree problem is usually solved.

Figure 15. Network model for the shortest path problem.

The network flow equivalent to the shortest path tree problem is formed
by equating arc distance to arc cost, assigning a fixed external flow of
*m* - 1 (*m* is the number of nodes) to the source node, and
assigning fixed external flows of -1 to every other node. This is illustrated
in Fig. 15. When solving this flow problem, the computer will assign flow
from the source to each node by the least cost path, since there are no
bounds on arc flows. The shortest path tree will consist of those arcs
with nonzero flow in the optimum solution. The solution to the example
is shown in Fig. 16.

Figure 16. Solution of the shortest path problem.