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.