Illustrate the execution of RELABEL-TO-FRONT in the manner of Figure 26.10 for the flow network in Figure 26.1(a). Assume that the initial ordering of vertices in Lis {Ï…₁, Ï…₂, Ï…₃, Ï…₄} and that the neighbor lists are

Ï…₁:N = {s, Ï…₂, Ï…₃} ;

Ï…₂:N = {s, Ï…₂, Ï…_{3 ,} υ₄} ;

Ï…₃:N = {s, Ï…₂, Ï…_4 ,t} ;

Ï…₄:N = {Ï…₂, Ï…_3 ,t} ;

Figure 26.10 The action of RELABEL-TO-FRONT. (a) A flow network just before the first iteration of the while loop. Initially, 26 units of flow leave source s. On the right is shown the initial list L = {x, y, z}, where initially u = x. Under each vertex in list L is its neighbor list, with the current neighbor shaded. Vertex x is discharged. It is relabeled to height 1, 5 units of excess flow are pushed to y, and the 7 remaining units of excess are pushed to the sink t. Because x is relabeled, it moves to the head of L, which in this case does not change the structure of L. (b) After x, the next vertex in L that is discharged is y. Figure 26.9 shows the detailed action of discharging y in this situation. Because y is relabeled, it is moved to the head of L. (c) Vertex x now follows y in L, and so it is again discharged, pushing all 5 units of excess flow to t. Because vertex x is not relabeled in this discharge operation, it remains in place in list L.

Figure 26.1 (a) A flow network G = (V,E) for the Lucky Puck Company’s trucking problem. The Vancouver factory is the source s, and the Winnipeg warehouse is the sink t . The company ships pucks through intermediate cities, but only c(u, ν) crates per day can go from city u to city ν. Each edge is labeled with its capacity. (b) A flowf in G with value |f| = 19. Each edge (u, ν) is labeled by f (u, ν )/c(u, ν). The slash notation merely separates the flow and capacity; it does not indicate division.