• The Ford-Fulkerson method (G,S,t) is iterative
  • This method depends on three ideas:
    • Augmenting paths
    • Residual networks
    • Cuts
  • Simplified Pseudo-code:
    initialize flow f to 0
    while there exist an augmenting path p
        do augmented flow f along p
    return f

Augmenting Paths

  • An augmenting path p is a simple path from source S to sing t in the residual network
  • Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

  • Definition: Each edge (u,v) on an augmenting path admits some additional positive flow u to v without violating the capacity constrain on the edge.
  • Example:


  • Minimum cut of a network: A cut whose capacity is minimum over all cuts on the network.
  • Max-flow min-cut theorem: A flow is maximum if and only if its residual network contains no augmenting path.
  • Example: cut(\{S, v_{1}, v_{2}\}), \{v_{3}, v_{4}, t\})
    Net-flow Across Cut (including net-flow between vertices): f(v_{1}, v_{3}) + f(v_{2},v_{3}) + f(v_{2}, v_{4}) = 14 + (-4) + 11 = 19
    Capacity (only edges going from source S to sink t): c(v_{1}, v_{3}) + c(v_{2}, v_{4}) = 12 + 14 = 26



// Comments
Ford-Fulkerson (G,S,t)
for each edge (u,v)\epsilon E[G]
do f[u,v]\leftarrow 0 // f:flow
do f[v,u]\leftarrow 0
while there exist a path p from S to t in the residual network Gf
do cf(p)\leftarrow min\{cf(u,v): (u,v) is in p \} // cf: residual capacity
for each edge (u,v) in p
do f[u,v]\leftarrow f[u,v]+cf(p) // p: path
do f[v,u]\leftarrow -f[u,v]


Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is O(V+E

Total running time is O(E|F*|) where f* is the maximum flow found


Note: If you find any mistake please let me know

© 2015, Alejandro G. Carlstein Ramos Mejia. All rights reserved.


Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.


Click to Insert Smiley

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeletonBunnyCatCat 2ChickChickenChicken 2CowCow 2DogDog 2DuckGoatHippoKoalaLionMonkeyMonkey 2MousePandaPigPig 2SheepSheep 2ReindeerSnailTigerTurtleBeerDrinkLiquorCoffeeCakePizzaWatermelonBowlPlateCanFemaleMaleHeartBroken HeartRoseDead RosePeaceYin YangUS FlagMoonStarSunCloudyRainThunderUmbrellaRainbowMusic NoteAirplaneCarIslandAnnouncebrbMailCellPhoneCameraFilmTVClockLampSearchCoinsComputerConsolePresentSoccerCloverPumpkinBombHammerKnifeHandcuffsPillPoopCigarette