2

Floyd-Warshall アルゴリズムをどのように変更して、O(V^3) 時間の計算量を維持する有向グラフの負のコスト サイクルの最短経路を見つけることができますか?

4

1 に答える 1

7

すべてのパスについて、負のサイクルを持つグラフに最短パスはありません。サイクルをもう一度トラバースすることで、より短いパスを見つけることができます。

Shortest Simple Pathを参照している場合(各頂点は最大で 1 回訪問できます) - P=NPでない限り実行できません。おそらくそうではありません。

効率的な最短単純パス アルゴリズムがあるとしますA。 最長経路問題のインスタンスとグラフ
が与えられた場合、新しいグラフを作成します。でを呼び出すと、 での最短の単純なパスが得られます。これは での最長のパスです。G=(V,E,w)G'=(V,E,w')w'(u,v) = -1*w(u,v)AG'G'G

ただし、Longest Path はNP-Hardであるため、P=NP でない限り、このようなソリューションは不可能です。

tl;dr:

  • 負のサイクルを持つグラフでは、最短経路などはありません。
  • 時間の負のサイクルを含むグラフで最短の単純なパスを見つけることはできませんO(V^3)(P=NP を除き、その場合でも O(V^3) であるとは限りません)。
于 2015-02-24T18:52:23.950 に答える