最小費用最大流及演算法

Ⅰ 最小費用最大流問題演算法舉例

最小費用最大流問題的演算法舉例主要包括Augment Path方法和預推進演算法及其變種。

1. Augment Path方法 核心思想：通過不斷搜索從源點到匯點的增廣路，將該路徑上的容量減去最小值，並在反向路徑上增加或擴大容量，以實現從源點到匯點的最大流量。 特點：確保每次操作都能增加網路中的流，從而避免陷入死循環。但在極端情況下，每次只能將流擴大1，因此效率較低，需要藉助其他演算法來提高效率。

2. 預推進演算法 核心操作：壓入和重標記。壓入操作將邊的始點預流盡可能多的壓向終點，重標記操作將頂點的高度設為所有鄰接點的高度的最小值加一。 變種： RelabeltoFront：維護一個溢出頂點的鏈表，通過Discharge操作不斷使頂點不再溢出，直至所有頂點的高度增加。時間復雜度為O。 Highest Label Preflow Push：與RelabeltoFront本質上沒有區別，但每次前移的都是高度最高的頂點，復雜度為O。 優化：Gap Heuristic，該優化在存在整數k時，對所有滿足h[v]=k的頂點進行更新，以提高演算法性能。

3. 演算法應用 在經濟學和管理學中，最小費用最大流問題用於尋找在給定容量和費用限制下，如何選擇路徑和分配流量以達到費用最小的要求。例如，n輛卡車從A地到B地運送物品，每條路段有不同的路費和容量限制，最小費用最大流問題即指如何分配卡車的出發路徑以達到費用最低，同時確保物品全部送到。