The Maximum Flow ProblemSlide 2Slide 3PowerPoint PresentationSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Solution to Maxflow problemSlide 12Slide 13Slide 14Slide 15The basic Ford Fulkerson algorithmThe basic Ford Fulkerson algorithm example of an executionSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Running TimeExampleSlide 36Slide 37Slide 38Slide 39The Maximum Flow Problem•The historically first and most fundamental network flow problem is the Maximum Flow Problem.The Maximum Flow Problem•Model–Given a network with N nodes and links among them. We would like to transport some entity (for example, data) from a source node to a destination node so that it flows along the links. The goal is to determine the maximum possible amount of flow that can be pushed through the network, such that link capacity contraints are obeyed and at the intermediate nodes (also called transshipment nodes) the flow is conserved, i.e., whatever flows into an intermediate node, the same amount must flow out.The Maximum Flow Problem•Let us review the input for the problem, the objective and constraints and then let us formulate it as a linear programming task.•Input data:–The capacity of the i → j link is Cij ≥ 0 (i, j = 1,…,N).–There are two distinguished nodes: the source (s) and the destination (d).•Remarks:–The links are directed in this model, Cij and Cji may be different.–If the link from i to j is missing from the network, then Cij = 0: Thus, the capacities automatically describe the network topology, too.•Constraints:–Capacity constraint: The flow on each link cannot exceed the capacity of the link.–Flow conservation: The total outgoing flow of a node is equal to the total incoming flow of the node, except for the source and the destination.•Objective:–Find the maximum amount of flow that can be sent through the network from the source to the destination, such that the link capacity is not exceeded on any link and the flow conservation constraint is satisfied at every intermediate (transshipment) node.•LP Formulation–Let xij denote the flow on link (I, j): (The values of these variables are not known in advance, we want to optimize them.)Solution to Maxflow problem•Solving the Maximum Flow Problem directly as a linear program, although possible, is not economical. There are several special algorithms which utilize the special structure of the problem and, therefore, are faster and simpler than a general LP solution.Solution to Maxflow problem•Historically, the first and most fundamental maximum flow algorithm is due to Ford and Fulkerson. The key idea of the algorithm is that if we can find a so called augmenting path, then the flow can be increased without violating any constraints.•An augmenting path is any undirected path from s to d, such that on any forward edge (an edge whose direction agrees with the path traversal) the flow is less than the capacity, while on any backward edge (an edge with opposite direction to the path traversal) the flow is positive.•If such an augmenting path is found then by increasing the flow on the forward edges and decreasing with the same amount on the backward edges we can increase the net flow out of the source, without constraint violation.•An augmenting path, if exists, can be found by a shortest path computation in an auxiliary graph, called residual graph, which is easily constructed from the original, using the current flow. If no augmenting path exists, then the flow is necessarily maximum.1 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf (p) = min {cf (u, v) | (u, v) is in p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf (p) 8 f [v, u] = - f [u, v] The basic Ford Fulkerson algorithmThe basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v41013121644 1420791 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 whil e there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf(p) 8 f [v, u] = - f [u, v] (residual) network GfThe basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v40/100/130/120/160/40/4 0/140/2070/9(residual) network Gf 1 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 wh ile there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf(p) 8 f [v, u] = - f [u, v]The basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v41013121644 142079(residual) network Gf 1 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf(p) 8 f [v, u] = - f [u, v]The basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v41013121644 142079(residual) network Gf temporary variable:cf (p) = 121 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf(p) 8 f [v, u] = - f [u, v]The basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v41013121644 142079(residual) network Gf temporary variable:cf (p) = 12S tv1v2v3v4101312/1212/1644 1412/2079new flow network G 1 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u, v) in p 7 do f [u, v] = f [u, v] + cf(p) 8 f [v, u] = - f [u, v]The basic Ford Fulkerson algorithmexample of an executionS tv1v2v3v4101312444 14879(residual) network Gf S tv1v2v3v4101312/1212/1644 1412/2079new flow network G 1212 1 for each edge (u, v) E [G] 2 do f [u, v] = 0 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf 5 do cf(p) = min{cf(u, v) | (u, v) p} 6 for each edge (u,
View Full Document
Unlocking...