9

このアルゴリズムを有向グラフに実装しています。しかし、このグラフノードの興味深い点には、独自のフロー容量もあります。元の問題のこの微妙な変更は、特別な方法で処理する必要があると思います。なぜなら、元の最大フロー問題では、最初から最後まで任意のパスを見つけることができました（実際、エドモンズ・カープアルゴリズムでは、BFSを実行し、最後のノードに到達する最初のパスを選択する必要があります）しかし、このノードでは-容量の拡張については、「このパスの選択」ジョブについてさらに注意する必要があります。私は元のアルゴリズムを実装し、max-flowよりも小さいフロー値を取得していることに気付いたので、それがこのノード容量の制限に関係しているとは思えないので、私はそれを知っています。

私はこれに多大な努力を払い、自己ループを追加することによって（各ノードに自己ループを追加し、それぞれのこの自己ループを含むパスを見つけることによって、ノードに容量の制約がないグラフに初期グラフを変換するなどのいくつかのアイデアを思いつきましたパス上のノード）または初期のノード容量の制約に優先する重みを持つ仮想ノードとエッジを追加する）ただし、これらのいずれかがこの問題の優れた解決策であるとは確信していません。

どんなアイデアでも大歓迎です。

前もって感謝します。

4

1 に答える 1

13

ノード容量の最大フロー問題から通常の最大フロー問題への単純な削減があります。

グラフ内のすべての頂点について、2つの頂点とvに置き換えます。するすべての入力エッジはを指す必要があり、からのすべての出力エッジはを指す必要があります。次に、からへの1つの追加エッジを、頂点の容量である容量で作成します。v_inv_outvv_invv_outv_inv_outc_vv

したがって、変換されたグラフでEdmunds-Karpを実行するだけです。

したがって、問題に次のグラフがあるとします（頂点のv容量は2です）。

s --> v --> t
   1  2  1

これは、最大フロー問題のこのグラフに対応します。

s --> v_in --> v_out --> t
   1        2         1

得られた最大フローが解決策であることは明らかです（そして証明することも特に難しいことではありません）。

于 2012-01-06T00:36:00.183 に答える