A Labeling Algorithm forthe Maximum-FlowNetwork ProblemAppendix CNetwork-flow problems can be solved by several methods. In Chapter 8 we introduced this topic by exploringthe special structure of network-flow problems and by applying the simplex method to this structure. Thisappendix continuesthe analysis of network problemsby describingthe applicationof thelabeling algorithmtothe maximum-flow network problem. Labeling methods provide an alternative approach for solving networkproblems. The basic idea behind the labeling procedure is to systematically attach labels to the nodes of anetwork until the optimum solution is reached.Labeling techniques can be used to solve a wide variety of network problems, such as shortest-pathproblems, maximal-flow problems, general minimal-cost network-flow problems, and minimal spanning-tree problems. It is the purpose of this appendix to illustrate the general nature of the labeling algorithms bydescribing a labeling method for the maximum-flow problem.C.1 THE MAXIMAL-FLOW PROBLEMThe maximal-flow problem was introduced in Section 8.2 of the text. If v denotes the amount of materialsent from node s, called the source, to note t, called the sink, the problem can be formulated as follows:Maximize v,subject to:Xjxij−Xkxki=v if i = s,−v if i = t,0 otherwise,0 ≤ xij≤ uij, (i = 1, 2, . . . , n; j = 1, 2, . . . , n).We assume that there is no arc from t to s. Also, uij= +∞ if arc i–j has unlimited capacity. Theinterpretation is that v units are supplied at s and consumed at t.Letting xtsdenote the variable v and rearranging, we see that the problem assumes the following specialform of the general network problem:Maximize xts0subject to:Xjxij−Xkxki= 0 (i = 1, 2, . . . , n)0 ≤ xij≤ uij(i = 1, 2, . . . , n; j = 1, 2, . . . , n).531532 A Labeling Algorithm for the Maximum-Flow Network Problem C.1Here arc t − s has been introduced into the network with utsdefined to be +∞, xtssimply returns the v unitsfrom node t back to node s, so that there is no formal external supply of material. Let us recall the example(see Fig. C.1) that was posed in Chapter 8 in terms of a water-pipeline system. The numbers above the arcsindicate flow capacity and the bold-faced numbers below the arcs specify a tentative flow plan.Figure C.1The algorithm for finding maximal flow rests on observing two ways to improve the flow in this example.The following two ‘‘paths’’ appear in Fig. C.1In the first case, the directed path 1–3–6 has the capacity to carry 2 additional units from the source tothe sink, as given by the capacity of its weakest link, arc 3–5. Note that adding this flow gives a feasible flowpattern, since 2 units are added as input as well as output to both of nodes 3 and 5.The second case is not a directed path from the source to the sink since arc 2–4 appears with the wrongorientation. Note, however, that adding one unit of flow to the ‘‘forward arcs’’ from 1 to 6 and subtractingone unit from the ‘‘reverse arc’’ 2-4 provides a feasible solution, with increased source-to-sink flow. Massbalance is maintained at node 4, since the one more unit sent from node 3 cancels with the one less unit sentfrom node 2. Similarly, at node 2 the one additional unit sent to node 5 cancels with the one less unit sent tonode 4.The second case is conceptually equivalent to the first if we view decreasing the flow along arc 2-4 assending flow from node 4 back to node 2 along the reverse arc 4-2. That is, the unit of flow from 2 to 4increases the effective capacity of the ‘‘return’’ arc 4-2 from 0 in the original network to 1. At the sametime, it decreases the usable or effective capacity along arc 2-4 from 3 to 2. With this view, the second casebecomes:Now both instances have determined a directed flow-carrying path from source to sink, that is, a directedpath with the capacity to carry additional flow.The maximal-flow algorithm inserts return, arcs, such as 4–2 here, and searches for flow-carrying paths.It utilizes a procedure common to network algorithms by ‘‘fanning our’’ from the source node, constructingflow-carrying paths to other nodes, until the sink node is reached.The procedure starts by labeling all nodes with the capacity to receive flow from the source node by asingle arc. For the pipeline example, arc 1–2 is saturated and has a zero effective capacity, whereas are 1–3can carry 8 additional units. thus, only node 3 is labeled from the sourceC.1 The Maximal-Flow Problem 533The procedure is repeated by labeling all nodes with the capacity to receive flow directly from node 3 bya single arc. In this case, nodes 4 and 5 are labeled and the labeled nodes become:Additional nodes can now be labeled from either node 4 or 5. If node 4 is selected next, then node 2 islabeled, since the effective capacity (return capacity) of arc 4-2 is positive (node 6 cannot be labeled fromnode 4 since arc 4-6 is saturated). The labeled nodes are:At any point in the algorithm, some of the labeled nodes, here nodes 1, 3 and 4, will already have beenused to label additional nodes. We will say that these nodes have been scanned. Any unscanned labeled nodecan be selected and scanned next.Scanning node 2 produces no additional labelings, since node 2 can only send flow directly to nodes 1,4, and 5, and these have been labeled previously. Node 6 is labeled when node 5 is scanned, and the labelednodes are:A flow-carrying path has been identified, since the sink has been labeled. In this case, the path discoveredis 1–3–5–6, which was the first path given above. The flow along this path is updated by increasing theflow along each arc in the path by the flow capacity of the path, here 2 units. Effective capacities are nowrecomputed and the labeling procedure is repeated, starting with only the source node labeled.Following is a formal description of the algorithm and a solution of the water-pipeline example. Noticethat the flow value on the arcs need not be recorded from step to step in the algorithm since this informationis computed easily from the effective (or usable) capacities of the arcs and their return arcs. For the exampleabove, the effective capacity on arc 2–4 is less than its initial capacity.The difference 3 = 2 − 1 must be the flow value on that arc that resulted in the reduced capacity. Theeffective capacity on arc 4–2 has been increased from 0 to 1 by adding return-flow capacity to that arc, not534 A