9

有向グラフで負の重みサイクルを見つけるアルゴリズムについて考えていました。問題は次のとおりです。グラフG（V、E）があり、負の重みを持つサイクルを見つけるための効率的なアルゴリズムを見つける必要があります。このPDFドキュメントのアルゴリズムを理解しています

簡単に言うと、このアルゴリズムは、| V | -1回反復して緩和を行うことにより、ベルマンフォードアルゴリズムを適用しています。その後、さらにリラックスできるエッジがあるかどうかをチェックし、負の重みサイクルが存在し、親ポインターによってそれをさかのぼることができ、すべてがうまくいくと、負の重みサイクルが見つかります。

ただし、グラフ上で深さ優先探索（DFS）を使用して、移動した距離のこれまでの合計を追跡する別のアルゴリズムを考えていました。最初はすべてのノードを白でマークし、私がいるときは灰色にします。パスを検索し、終了時に黒でマークします。これにより、訪問したノードが見つかり、それが（パス内で）灰色であり、深さによってすでに終了している黒ではない場合にのみ、サイクルが見つかることがわかります。 -最初の検索なので、私のアルゴリズムでは、すでにアクセスした灰色のノードに到達した場合、更新内容（新しい距離）を確認し、以前よりも低い場合は、負の重みがあることがわかりますサイクルし、それをさかのぼることができます。

私のアルゴリズムは間違っていますか？もしそうなら、あなたは反例を見つけることができますか？そうでない場合は、私がそれを証明するのを手伝ってくれませんか？

ありがとうございました

4

4 に答える 4

17

ベルマンフォードは常に機能するとは限りません。問題は、単一ソースの最短パスアルゴリズムです。選択したソースから負のループに到達できない場合、失敗します。ただし、ベルマンフォードに少し変更を加えると、ソース頂点を選択してその距離を0に初期化する代わりに、すべての距離を0に初期化してから、ベルマンフォードを実行できます。これは、重みエッジが0の元のグラフのすべての頂点を指す頂点s'を追加することと同じです。ベルマンフォード法がグラフ上で実行され、d [u] + w [u] [v] <d [v]となる頂点uとエッジ（u、v）が見つかったら、負のサイクルが必要であることがわかります。 uに向かって、前のグラフのuからさかのぼると、サイクルが見つかります。

DFSはまったく機能しません。明らかに、考えられるすべてのサイクルを使い果たすことはできません。DFSを使用して、グラフ内のサイクルの存在を見つけることができますが、それ以上はできません。

于 2012-10-21T05:49:31.590 に答える
3

明らかな問題の1つは、ノードにマークを付けることです。 

 A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

パスA->B->Dをたどると、Dを押すとABDは灰色になります。サイクルが見つかりません。あなたはAに飛び出します。BとDは黒です。あなたはエッジを取ります、Dが黒であるため、サイクルは見つかりません。

一般に、パスの数はグラフのサイズに対して指数関数的です。すべてのパスを試す必要があります。ここでノードをマークする方法はありません。有向グラフの各エッジ方向を個別に処理した場合、エッジをマークすることは可能だと思いますが、これはすべてのパスを列挙することと同じです。

于 2011-04-05T23:03:29.073 に答える
-1

これを線形時間で解決する方法があると思います。深さ優先探索でグラフを検索している間（DFSの実行時間はO（V + E））、ソースから現在のノードまでの距離を追跡できます（親の距離を重みでインクリメントするだけです）。子ノードを親に接続するエッジ）。次に、サイクルに遭遇するたびに（サイクルは、無向グラフでバックエッジを見つけるか、有向グラフでバックエッジまたはフォワードエッジを見つけることで検出されます）、ソースノードとルートノードの間の距離を差し引くことができます。ソースノードとサイクルの最後のノード（ルートノードはサイクルが開始されたノード）の間の距離からサイクルします。結果が負の場合、サイクルは負でなければなりません！

于 2013-11-15T21:26:56.510 に答える
-1

2003年のYamada/Kinoshitas Algorithmは、検出されたサイクルの最大頂点数の上限を使用して、有向加重グラフですべての負の加重サイクルを見つける問題を解決します。

ただし、実装するのは非常に困難です。

概要

エッジが必ずしも正ではない重みに関連付けられている有向グラフを考えると、負の合計重みを持つすべての基本サイクルを見つける問題に関心があります。すべての基本サイクルを見つけるためのアルゴリズム、または存在する場合はそのようなグラフの負のサイクルを検出するためのアルゴリズムが十分に検討されています。ただし、負のコストですべての基本サイクルを見つけることは未踏のようです。「分割統治」パラダイムに基づいてこれを行うアルゴリズムを開発し、いくつかの数値実験でそのパフォーマンスを評価します。

2002年5月からDiscreteAppliedMathematics 118（3）：279-291 https://www.researchgate.net/publication/220570430_Finding_all_the_negative_cycles_in_a_directed_graph

于 2020-12-28T03:40:18.400 に答える