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
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.