最小費用流

辺eにはコストd(e)と容量c(e)が定まっていて、sからtへ流量Fのフローを流したときの全ての辺の流量×コストの和が最小になる時の費用を求める問題。

これは単純で、最大流のときとほぼ同じです。残余グラフを考えて、そこでコストを考慮して最短路に沿って流せば良いのです。残余グラフにおけるコストは押し戻しなので、マイナスの値になります。つまりベルマンフォードのアルゴリズムを使えば良いです。このとき、常に最小費用流、つまり最適な解を選んでいけば、残余グラフに負の閉路は存在しません(だからベルマンフォードが使える)。

このことを用いると、数学的帰納法で簡単にこのアルゴリズムが最小費用流になるということがわかります。

ちなみにこれだとベルマンフォードを使っているのでそこそこ時間がかかってしまいます。
ということでダイクストラ法を使いたいですね。ダイクストラ法を使うには、辺のコストが全て正でなければなりません。ここでボテンシャルhという考え方を導入します。辺のコストをd'(e) = d(e) + h(u) - h(v)という形で更新してあげることで、d'(e)が全て正になり、かつ最小費用流には影響を与えないようにします。h(v) = (s-v間の最短距離)とすることでそれが成立するらしいです(確かにそうであることは理解できるけど…)。

よってO(Elog(V))で計算できるようになりました。

ちなみに、このポテンシャルという考え方自体は双対問題を考えると自然と出てくる考え方だそうです。ココらへんはまだよくわからないのでそのうちまとめようと思います。離散数学勉強しないと…。