增廣演算法

A. 網路流理論求最大流有兩種常用的演算法

網路流理論中求解最大流問題，有兩類常用的演算法，其中之一是augment path，即「增廣路」演算法。該演算法的基本思路如下：

首先，我們從原始網路G出發，構建輔助圖G'，其頂點V(G')與G相同，初始邊的容量E(G')與E(G)一致。每次操作中，從源點Source開始，尋找一條從Source到Sink的路徑。沿著這條路徑，將每條邊的容量減去路徑上容量最小值，然後對路徑上每條邊，在其反方向增加或擴展容量，即剛才減去的容量。這個過程會一直持續，直到無法找到新的路徑為止。此時，輔助圖G'上的正向流量即為最大流。

雖然直觀上可能會擔心演算法會陷入無限循環，實際上，由於每次操作都增加了從Source到Sink的流量，且假設容量和流都是整數，這個過程會自然終止。尋找路徑時，可以選用DFS或BFS搜索演算法，BFS通常比DFS更快，但代碼量也會相應增加。

然而，augment path方法的一個局限是，在極端情況下，每次只能將流擴大1，這在性能上造成較大影響。為解決這個問題，另一種更復雜的演算法就是預推進（push label）演算法。預推進演算法能夠更有效地處理大規模數據，提高求解最大流的效率，雖然它可能需要更復雜的實現，但其性能優勢顯而易見。

所謂網路或容量網路指的是一個連通的賦權有向圖D＝（V、E、C），其中V是該圖的頂點集，E是有向邊(即弧)集，C是弧上的容量。此外頂點集中包括一個起點和一個終點。網路上的流就是由起點流向終點的可行流，這是定義在網路上的非負函數，它一方面受到容量的限制，另一方面除去起點和終點以外，在所有中途點要求保持流入量和流出量是平衡的。