Minimum Cost Flow

Minimum Cost Flow 演算法之筆記

1.Cycle Canceling Algorithm

在實施Maximum flow演算法後執行此演算法可求出最小成本最大流(Minimum cost maximum flow)。

圖1:cycle-canceling algorithm

步驟：
先找到網路圖中的一個可行流(feasible flow)，接著在剩餘網路圖G(x)中不斷地尋找負環並且更新剩餘網路圖G(x)，直到沒有負環即為Minimum Cost Flow。

定理：

Negative Cycle Optimality Condition. A feasible solution x* is an optimal solution of the minimum cost flow problem if and only if the residual network G(x*) contains no negative cost directed cycle.

證明略。

Find Negative Flow方式：
1.Label Correcting Algortihm 
2.Bellman-Ford Algorithm

以上兩演算法皆使用原使用時不允許負環之特性進而找出負環

Time Complexity Analysis:

n:number of nodes,m:number of edges,

 Let U = max(v,w) ∈ E     u(v,w)       圖上的邊中最大的capacity
 Let C = max(v,w) ∈ E  │c(v,w)│     圖上的邊中最大的cost
 For any feasible flow -mCU ≦ c(f) ≦  mCU

因為成本計算為邊上的flow*cost，所以最初的最大成本不會超過mCU，若成本不為負，則最少為0，可為負數，則最少為-mCU；而每次while迴圈更新後成本至少減少1。
綜合以上，迴圈最多執行2mCU次。

 Time to find a feasible flow: O((n+m)nm)
 Time to find negative cycle: O(nm)

 Running time = O(nm^2CU) . Not polynomial.

2.Successive Shortest Path Algorithm

仿Ford-Fulkerson演算法，不斷尋找成本最小的擴充路徑。

Reference：
圖1:New Polynomial-Time Cycle-Canceling Algorithms for Minimum Cost Flows / P. T. Sokkalingam*, Ravindra K. Ahuja** , and James B. Orlin***(https://pdfs.semanticscholar.org/9795/ffbb16815bc3afbdba6f78d00824e8728997.pdf 
 )
1.Lecture 12:Basic Algorithms for Min Cost Flow,Reading: AM&O Sections 9.3,9.6, 9.7
歡迎討論，轉載請標明出處，謝謝。