algorithm - ユニット キャパシティ エッジをもつフロー ネットワークにおける Ford-Fulkerson 法の時間計算量

Question

Ford-Fulkerson アルゴリズムは、単位容量フロー ネットワーク (すべてのエッジに単位容量がある) の最大フローを、時間内にn頂点とmエッジで見つけますO(mn)か?

Answer 1

O(M*f)は、容量が整数のグラフでの Ford-Fulkerson の既知の実行時間の推定値です。ここMで、 はエッジの数とf最大フローの値です。これは、それぞれの拡張パスを簡単に見つけることができO(M)、そのようなパスごとにフローが で増加するためです。少なくとも 1。

グラフに重複するエッジがなく (つまり、同じ開始頂点と終了頂点を持つエッジのペアがない)、各エッジに単位容量がある場合、最大フローfは頂点の数を超えませんN(単にN-1ソースからのエッジしかないため、複雑さは確かにO(N*M).

ただし、グラフが重複するエッジを持つことが許可されている場合 (それでも各エッジの容量は 1 です)、 はfよりも大きくなりN、最大でMになり、時間の複雑さは になりO(M*M)ます。このような複雑さが生じます。