Minimum Cost Flow

這真是一個蠻麻煩的東西耶XP

－最小成本流量問題－

今天了解的大概是這樣：

演算法名稱::『最短成本路線流漸增式演算法』（亂取的XD）

演算法內容:: 用『某種可以求有負邊的最短路演算法』求最短路（cost）＋盡量流過去～

演算法條件::

1. 要求由s到t流動f的最小花費（這就是演算法目的X)）

2. 沒有負環（原因看證明）

演算法證明::

1. 證明『f=最小成本流量，若且為若剩餘圖沒有負環』

pf: 設 f ' 小於 f ( 在某圖以某相同流量流動的花費 )

(1) 流量相同 -> 差異為一個環（f ' - f 的流量圖，任一點入度＝出度）

(2) f ' 小於 f ＆ (1) -> 差異為一個負環（f ' + (-f){邊正負顛倒}小於零，那個差異是負的）

若剩餘圖有負環，因f ' - f = 負環，故f ' = f + 負環，得證。

2. 證明『每次都取s到t的最短路，就會是最小成本流量』

pf: 數學歸納法

(1) 因圖沒有負環，f0 = 最小成本流量 = 零

(2) 若fi 是最小成本流量，fi+1 是 fi + （s到t的最短路徑），故fi+1 也是最小成本流量。（反證法：若有另一路徑f 'i+1 比fi+1 小，因fi+1 是 fi + （s到t的最短路徑），但卻存在一更小成本流量，由第一個證明得知這個圖有負環，而且是fi 的問題（因為s到t是最短路徑，無更短的），那麼fi 就不是最小成本流量，故矛盾，假設不成立）