Minimum Cost Flow Algorithm

個人的メモ

費用を距離とみた最短経路に沿ってフローを流し続けることで解を得る. すべての辺の容量および流すフローの流量が整数の場合は最適解が有限なら最小費用流でかつすべての辺について流れるフローの流量が整数値となるようなものが存在する(有向グラフの接続行列の完全単模性みたく言える).
以下の実装ではすべての辺が非負コストであることを仮定して Dijkstra 法 で求めている.
一般には残余ネットワーク上での最短経路問題は負辺を含むため直接 Dijkstra 法を適用することはできないが, 初めのステップでポテンシャル $p$ (頂点 $s$ から各頂点への最短経路とする) を計算すればそれ以降は各頂点のポテンシャルに最短距離コストを足して更新していくことで常に各辺は非負重みであるかのように扱える. ここで更新の際に各頂点に最短距離コストを足すことでポテンシャルの条件(辺 $e = (u, v)$ について $e.cost + p[u] - p[v] \geq 0$) が更新後の残余ネットワーク上でも成り立つようにできていることが確認できる.
初めのポテンシャルの計算だが, 負辺を含む(負の有向閉路は含まない)なら Bellman Ford, グラフが DAG なら トポソDP などが考えられる.
負の有向閉路が合った場合は こちらのアルゴリズム が参考になると思う.

(補足)
アルゴリズムは Primal-Dual(主双対) 法と眺めることができ, 相補性条件を書き下すと $f$ が主問題の実行可能解である場合, 残余ネットワーク上のすべての辺 $e = (u, v)$ について $e.cost + p(u) - p(v) \ge 0$, つまり残余ネットワーク上で valid なポテンシャル $p$ が存在することが必要十分条件と成ることが分かる. アルゴリズムで初めにすべての頂点 $u$ について $p[u] = 0$ に設定しているが, これは最小費用流問題を線形計画問題と見たときのその双対問題の実行可能解かつ相補性条件(に相当するもの) を満たすものを初期値に取っていることに対応する. 負のコストの辺が無い場合には確かに残余ネットワーク上のすべての辺 $e = (u, v)$ について $e.cost + p[u] - p[v] \geq 0$ が成り立ち, $p$ が valid なポテンシャルとなっていることが確認できる. 相補性条件を道標として $p$ を更新して最終的にフローを流し終えたとき, つまり $f$ が主問題の実行可能解に入ったときに操作を終了する. よって操作を終了したときには最適解が得られていることがわかる.