file:///C:/DOCUME%7E1/fox1987/LOCALS%7E1/Temp/moz-screenshot-2.png从源点开始,找到一个仍有剩余能力的路径,标注剩余能力,剩余能力标注为当前的剩余能力和前一跳剩余能力的较小值,直到标注到汇点。每次寻找下一跳结点按照编号从小到大的顺序如下图所示:源点是VS
,汇点是VT。从VS开始,VS到V1的路径没有剩余能力了(5,5)(容量为5,流量也为5,满了),所以看VS到V2的路径(4,2),剩余能力为2(4-2)。所以当前的剩余能力为2,在v2处标记为【vs,2】,表示从vs流入,剩余能力为2,然后看v2到v5,当前剩余能力为3,上一结点v2的剩余能力为2,所以v5处标记为【v2,2】。

看v5到v1由于是v1流向v5的,所以标记为【-v5,2】(方向是负的,所以剩余能力直接取上一跳剩余能力即可),然后v1到v4的,剩余能力为3,所以v4处