3.4.4 other shortest-path problems

3.4.4 other shortest-path problems
Further sets of problems concern the maximum flow that can be passed between two points in a network. Clearly the capacity of in divide links may be constrained (see Figure 3.17), and the problem is to identify the path (or paths) that the maximum flow must follow. The problem of defining maximum flow' was solved in 1955 by Dantzig and Fulkerson through their max flow min cut theorem which showed that the maximum flow through a network was equal to the sum of the capacity of the branches of the minimum cut. A cut is any collection of branches which, when removed, separates two terminals in the network. Thus, in Figure 3.17, we can see that there are four possible cuts which separate A from D (these are plotted in Figure 3.17B). The minimum cut is the line ACBD with a total capacity of 6 units. This is also the maximum flow through this simple network (Figure 3.17c Locational selection of the paths which the maximum flow must follow posed few problems in this simple case. All links were employed, although two of them (shown by pecked lines) were carrying less than their total capacity. A number of algorithms for finding maximum flow paths through very complex networks have been evolved Ford and Fulkerson, 1962), but these are largely concerned with steady-state flow. Kleinrock's (1964) work has been with paths through networks where the flow is concerned, on the other hand not steady but fluctuating and rather unpredictable (e.g. messages through telephone networks): here stochastic simulation models for alternative arrangements of the network have proved valuable. Work on paths of this kind have direct analogies with flood routing problems on large river control networks The most complex of the path finding problems is that of finding a least cost flow path through a network. Ford and Fulkerson (1962, Chapter 3) suggest that something like half the time spent on industrial and military applications of linear programming (see Chapter 15) is concerned with this topic. Her do little more than point out the nature of the problem and the kind of path solutions that may be obtained. Figure 3.18 illustrates a simple example in determining minimal cost paths through a network while obtaining maximum flow (Ford and Fulkerson, 1962, pp. 123-127). The network consists of a set of 21 links (edges) joining the two terminal points (i). Figure 3.18A shows the maximum flow capacity of each link and Figure 3.18B the unit shipping costs. lf we assume our problem is to ship goods from i to j, then it is possible to compute that a positive m cost flow will get through the network to j by utilizing the paths shown by the arrows in Figure 3.18c However, for the maximum flow through the network (given the cost and capacity constraints) almost all the links are utilized Figure 3.18D). Two points worth noting are that (i) not all the links along the paths operate at their full capacity (the links which are not fully 'saturated' with traffic shown by broken lines) and (ii) the direction of flow along some are of the links may change as total flow through the network increases.