DRPDual(DmaxvAf+dvff≤0≤b≥0maxvAf+dvf-ffv≤≤≤≤≤00011forallrowsforrowswheref=binDforrowswheref=0inDWorkingthroughthetechnicalstepswegofromDtoDRP.DRPcanbeinterpretedassaying:Findapathπˉfromstotthatuses?SaturatedArcs:onlyinbackwarddirection?UnusedArcs:Onlyinforwarddirection?OtherArcs:Anydirection.Pathπwillbeindicatedbyπˉi,j=1if(i,jinthepath,and0,otherwise.16πisexactlyanaugmentingpathinaresidualnetworkoforiginal?owπ.Onewe?ndsuchapathweaddasmuchasmuch?owaspossiblealongtheresidualpathbysettingπ=π+θ1πˉwherewecanworkoutthatθ1isthebottleneckvaluealongpathπˉ.ThisisexactlytheFord-FulkersonaugmentingpathalgorithmforMax-Flow.17
