最小費用流のかいつまんだ(いい加減な)説明
ソースも図もないけれど、ライブラリのお話。
対象とする人
ダイクストラより重たいものは(ry。(ダイクストラ、と言われて分かる人。)賢い人向けのもっと専門的な説明はいくらでもあるので、いい加減だなぁ、うさんくさいなぁ、と思う場合はそちらをどうぞ。(あくまでこういう気持ちでやればなんとなく分かったつもりになれる、というのがこれを書いた意図です。)
大雑把な話(ここは最大流を知らないと分かりにくいかも...。)
たとえば流量Kの最小費用流を求めたい場合、K回始点から終点までの最小距離を計算してやれば良いらしいです。このときのポイントは、ちょっと前の最短路で通った道を、やっぱや〜めた、すると実はより良い結果になることがあります。そもそも流量Kを確保しないといけないので、どんなに最短路でも使えない場合があります。
この、やっぱや〜めた、を実現するために、最大流とか最小費用流とかのお話をするときは、ある道を通ったら、逆向きに道をつけかえる作業をします。しかもこのとき、その道を通るときには、元の距離の分だけ移動距離を減らすことができます。(通らなかったことにするのだから、トータルで見たらその分だけ総距離を返してくれるということですが。)
さて、ダイクストラのアルゴリズムでは、距離が負の値の道があるとおかしなことになるそうです。まさにこの逆向きの道がそうです。ダイクストラのアルゴリズムを無理やり拡張して、一度通った場所でも、前に来たときよりも短い移動距離で来ることができたら、引き続き探索する、という風にできますが、それだと最悪の場合、全部の道順を試すことになります。(滅多に最悪の事態にはならないので、ここまででいいや、というのもアリだと思います。)
ちょっと脇道
開始点を固定してダイクストラのアルゴリズムを実行すると、全部の点への最小距離が求まります。これを取り敢えずAという整数配列に入れたとします。次に、道がいくつか工事中で通れなくなったとして、同様にダイクストラのアルゴリズムを実行して、全部の点への最小距離をBという整数配列に入れてみましょう。
このとき、AとBを比較したときに、AよりもBが小さいということはあるでしょうか？ここではそういうことが起きないグラフに限定して話を続けます。(負の距離の道がないグラフに相当します。)
最小費用流の問題を考えるとき、このような道路工事があちこちで起きます。
でも負の距離の道が出てくるじゃん！
最小費用流の問題を考えるときに、工事中になる道は、必ず今までの最短路の一部です。
ここで、A->B、という道を例に考えます。もし、A->Bという道の逆向きの道B->Aを通る(つまりA->Bを使うのをやめる)ことによって、今までよりもAに短い距離の移動で到達できるとしましょう。このとき、Bへの最短距離からA->Bの移動距離を引いたものが、Aへの最短距離になるはずです。
一方、この前の段階で、A->Bの移動を含む最短路があるはずです。(これは最小費用流特有の性質です。)となると、このA->Bの移動をしようと思うに至ったということは、Aへの最短距離にA->Bへの移動距離を加えたものが、Bへの最短距離になります。
上の二つから、負の距離の道を通っても、Aへの最短距離は減ることがないと分かります。(もし減るとしたら、Aを通らないでBに到達するより近い道があったということで、前の段階で最短ではない道を選択したことになります。)
