最大フローのアルゴリズム

  • Edmonds-Karp
  • Dinic
  • Goldberg-Tarjan
  • Goldberg-Tarjan with gap heuristics

あたりを実装してベンチマークしてみた。

Edmonds-Karpはやっぱり他のアルゴリズムに比べると圧倒的に遅い(naiveなGoldberg-Tarjan除く)。N=1000くらいになると比べるべくもない。ymatsuさんに聞いていた通り、Goldberg-Tarjanはheuristicsが無いとあまり意味が無い。逆に、ちゃんと実装すると劇的に改善した。
しかし、意外と速いスピードを出していたのがDinicだったりしてちょっと驚いた。Goldberg-Tarjan with gap heuristicsとは大体同じくらいの速度。コンパクトに書けるならこれを選択するのもありかもしれないなあ。


(追記)
...という論文を今井先生が書いていた件。

(追記)
せっかくなので測定結果をはってみる。Edmonds-KarpとGoldbarg-Tarjan without heuristicsは問題外なので計測していない(たぶん1分以上かかる)。

ネットワークはランダムに0〜1000の整数値をキャパシティとする4000x4000の密行列を生成している。

// g++ -O0の場合
Benchmarking with N=4000
=== Case 1
Dinic: 0.641 secs. result=2009359.
Goldberg-Tarjan (gap): 1.140 secs. result=2009359.
Goldberg-Tarjan (gap + lift-to-front): 0.844 secs. result=2009359.
=== Case 2
Dinic: 0.828 secs. result=1966746.
Goldberg-Tarjan (gap): 1.188 secs. result=1966746.
Goldberg-Tarjan (gap + lift-to-front): 1.250 secs. result=1966746.
=== Case 3
Dinic: 0.735 secs. result=1977706.
Goldberg-Tarjan (gap): 1.141 secs. result=1977706.
Goldberg-Tarjan (gap + lift-to-front): 0.719 secs. result=1977706.
=== Case 4
Dinic: 0.828 secs. result=1987877.
Goldberg-Tarjan (gap): 1.156 secs. result=1987877.
Goldberg-Tarjan (gap + lift-to-front): 1.234 secs. result=1987877.
=== Case 5
Dinic: 0.812 secs. result=1970366.
Goldberg-Tarjan (gap): 1.156 secs. result=1970366.
Goldberg-Tarjan (gap + lift-to-front): 1.235 secs. result=1970366.

// g++ -O1の場合
Benchmarking with N=4000
=== Case 1
Dinic: 0.422 secs. result=2009359.
Goldberg-Tarjan (gap): 0.687 secs. result=2009359.
Goldberg-Tarjan (gap + lift-to-front): 0.468 secs. result=2009359.
=== Case 2
Dinic: 0.547 secs. result=1966746.
Goldberg-Tarjan (gap): 0.703 secs. result=1966746.
Goldberg-Tarjan (gap + lift-to-front): 0.718 secs. result=1966746.
=== Case 3
Dinic: 0.500 secs. result=1977706.
Goldberg-Tarjan (gap): 0.703 secs. result=1977706.
Goldberg-Tarjan (gap + lift-to-front): 0.406 secs. result=1977706.
=== Case 4
Dinic: 0.563 secs. result=1987877.
Goldberg-Tarjan (gap): 0.703 secs. result=1987877.
Goldberg-Tarjan (gap + lift-to-front): 0.718 secs. result=1987877.
=== Case 5
Dinic: 0.547 secs. result=1970366.
Goldberg-Tarjan (gap): 0.687 secs. result=1970366.
Goldberg-Tarjan (gap + lift-to-front): 0.703 secs. result=1970366.