最小費用流問題において最短増加パスの探索にダイクストラ法を使う

algorithm

はじめに

最小費用流を求める際には，フォードファルカーソンアルゴリズムにおける増加パスの探索アルゴリズムとして，
フローのコストを距離として最短路アルゴリズムを用いれば良い．
しかし，残余グラフの生成をするときにコストが負の枝を追加することになるためダイクストラ法は用いることができない．

これはダイクストラ法では少ないステップで終点に到達することと最短であることが等価であるとみなすが，コストが負の場合その枝を利用できるまで探索したほうがコストが小さくなることがあるからである．

そのため，ベルマンフォード法などによって最短路を求める必要がある．こちらのアルゴリズムはダイクストラ法に比べ計算量が多い．

しかし，ポテンシャルというのを導入することによりダイクストラ法を用いて最小費用流を求めることが出来る．

概要

重み付きグラフG=(N,E)上において辺(s,t)∈Eの重みd(s,t)をd'=d+h(s)-h(t)としても最短路が不変であることを利用し，グラフの重みを変換する．

具体的にh(u)としてs->u間の最短路上のコストを用いる．
このポテンシャル付きグラフをG'とするとG'上では最短路パス（＝G上の最短路パス）上においてすべての辺のコストが０となる．
よって残余グラフにおいて追加される辺のコストを０にすることができる．

これにより最小費用流問題においてダイクストラ法を用いることができる．



アルゴリズムの詳細

参考文献を参照ください．

参考文献

どこかの論文とかにありそうだけど発見ならず．