15.082 and 6.855JSlide 3Initialize DistancesSaturate Arcs out of node sSelect, then relabel/pushSlide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 2015.082 and 6.855J The Goldberg-Tarjan Preflow Push Algorithm for the Maximum Flow Problem4114212331s2453tPreflow PushThis is the original network, which is also the original residual network. 4114212331s2453t4114212331s2453tInitialize Distances4114212331s2453tThe node label henceforth will be the distance label.054321t4 53s2d(j) is at most the distance of j to t in G(x)0221114114212331s2453tSaturate Arcs out of node s4114212331s2453tSaturate arcs out of node s.054321t4 53s2Move excess to the adjacent arcs0221113212136ssRelabel node s after all incident arcs have been saturated.23 44114212331s2453tSelect, then relabel/push4114212331s2453tSelect an active node, that is, one with excess054321t4 53s2Push/Relabel0221113212136ssUpdate excess after a push114114212331s2453tSelect, then relabel/push4114212331s2453tSelect an active node, that is, one with excess054321t4 53s2022111321216ssNo arc incident to the selected node is admissible. So relabel.112334114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node, that is, one with excess054321t4 5s2022113226ssPush/Relabel1232131234114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s2022113226ssPush/Relabel123213123 31322154114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s202211226ssPush/Relabel12321312313214114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s202211226ssThere is no incident admissible arc. So Relabel. 12321312313212554114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t45s202211226ssPush/Relabel 12321323132221414114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t45s202211226ssThere is no incident admissible arc. So relabel. 12321323132221413554114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s202211226ssPush/Relabel123213231322214135534114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s202211226ssPush/Relabel12321322222413553114144114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s202211226ssPush/Relabel123213222224135531424224114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s02211226ssPush/Relabel12321322222413553144244114212331s2453tSelect, then relabel/push4114212331s245tSelect an active node.054321t4 5s02211226ssPush/Relabel1232132132241355314424 35554114212331s2453tSelect, then relabel/push4114212331s245tOne can keep pushing flow between nodes 2 and 5 until eventually all flow returns to node s.054321t4 5s02211226ssThere are ways to speed up the last iterations.1232132132241355314424 3555MITOpenCourseWarehttp://ocw.mit.edu15.082J / 6.855J / ESD.78J Network OptimizationFall 2010 For information about citing these materials or our Terms of Use, visit: