いくつかの負のエッジ重みを持つ重み付きDAGがあり、その中のすべての最短パスを見つけたいと思っています。O（n ^ 2）よりも複雑なアルゴリズムはありますか？（私のグラフは完全です。つまり、{1..n}の任意のi、jおよびi <jに対してエッジ（i、j）があります）。
ありがとう
2809 次
2 に答える
1
探しているアルゴリズムはO(n 3 ) で実行されるFloyd-Warshallです。
すべてのノードで Djikstra を実行すると、これよりもうまくいく場合があります。フィボナッチ ヒープを使用すると、O(n 2 log n + ne) を取得できます。ここで、e = エッジの数です。これを負のエッジ ウェイトで動作させることも可能です!
ただし、フィボナッチ ヒープには大きな定数があるため、実際には、このアプローチは非常にまばらなグラフに対してのみ高速になります。グラフが完成したと言ったので、Floyd-Warshall が最善の策です。
于 2012-08-14T06:43:47.180 に答える
1
于 2012-08-14T06:32:51.103 に答える