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
ndsuchapathweaddasmuchasmuch
owaspossiblealongtheresidualpathbysettingπ=π+θ1πˉwherewecanworkoutthatθ1isthebottleneckvaluealongpathπˉ
ThisisexactlytheFord-FulkersonaugmentingpathalgorithmforMax-Flow
