上一次我們把求最大流的問題轉(zhuǎn)化成了找到一條增廣路然后優(yōu)化的問題串绩。今天講講怎么找增廣路甩十。
Ford-Fulkerson算法（標號法）求增廣路胞四。
標號法的流程分為標記和調(diào)整兩個階段盔腔。在標記階段中壕曼，為圖中的每個頂點找一個優(yōu)化方案昼扛。在調(diào)整階段寸齐，利用標記階段的記號欲诺，重新分配流量∶祓校可以看出來扰法，標記法的核心是第一個階段，怎么為每個頂點找到一個優(yōu)化方案呢毅厚？很簡單塞颁，只需要兩個量就記下每個點的優(yōu)化方案了。一個數(shù)記錄需要優(yōu)化的弧連接的是哪個頂點吸耿，另一個數(shù)記錄能夠優(yōu)化的量祠锣。
在標記過程，網(wǎng)絡(luò)中的頂點可以分為三類：
① 未標號頂點咽安；
② 已標號伴网，未檢查鄰接頂點；
③ 已標號妆棒，且已檢查鄰接頂點澡腾。
標號過程開始時，總是先給Vs標上(0, +∞)糕珊，0表示Vs是匯點动分，+∞表示Vs可以流出任意多
的流量（先不討論與之連接的弧能不能吸收這些流量）。這時Vs是已標號而末檢查的頂點放接，其余都是末標號點刺啦。然后從源點Vs出發(fā)，使用廣度優(yōu)先搜索對它的每個鄰接頂點進行標號纠脾。
假設(shè)已標號而未檢查的頂點是u，對u的一個未標號頂點v：
a)若v與u“正向”鄰接蜕青，且在弧上目前分配的流量f(u, v)＜弧的容量c(u, v)苟蹈，則給v標號(u，L(v))右核，這里L(fēng)(v)= min{ L(u), c(u, v)–f(u, v)}慧脱，L(u)是頂點u能提供的標號，c(u,v)–f(u, v)是弧能接受的標號贺喝，取二者中的較小者菱鸥。這時頂點v成為已標號而末檢查的頂點。
b)若v與u“反向”鄰接躏鱼，且在弧< v, u>上f(v, u)＞0氮采，則給v標號( -u, L(v))，這里L(fēng)(v) =min{L(u), f(v, u) }染苛。這時頂點v成為已標號而未檢查的頂點鹊漠。
當u的全部鄰接頂點都已檢查后，u成為已標號且已檢查過的頂點。
重復(fù)上述步驟直至標記到目的地點躯概，若目的點可改進量α= 0登钥，或者不能給目的點標號，則算法結(jié)束娶靡，這時的可行流即為最大流牧牢。算法結(jié)束。一旦目的點Vt被標號并且第2個分量大于0姿锭，則表明存在一條從Vs到Vt的增廣路P塔鳍，接下來要進入調(diào)整過程；
調(diào)整過程采用“倒向追蹤”的方法艾凯，從Vt開始献幔，利用標號頂點的第一個分量逐條弧地找出增廣路P，并以Vt的第二個分量L(Vt)作為改進量α趾诗，改進P路上的流量蜡感。
