33

Dijkstra のアルゴリズムと Floyd-Warshall アルゴリズムについて調べています。Dijkstra は 1 つのノードから他のすべてのノードへの最適なルートを見つけ、Floyd-Warshall はすべてのノードのペアリングの最適なルートを見つけることを理解しています。

私の質問は、すべてのペアリング間の最適なルートを見つけるために、すべてのノードで実行すると、ダイクストラのアルゴリズムがフロイドのアルゴリズムよりも効率的であるかということです。

Dijkstra の実行時間は O(E + VlogV) で、Floyd の実行時間は O(V 3 ) です。ダイクストラが失敗した場合、この場合のランタイムはどうなるでしょうか? ありがとう!

4

4 に答える 4

43

他の人が指摘しているように、Floyd-Warshallは時間O(n 3)で実行され、ダイクストラの実装をバックアップするためにフィボナッチヒープを使用していると仮定して、各ノードから他のノードへのダイクストラの検索を実行します。2 log n)。ただし、ダイクストラのアルゴリズムは負のエッジの重みでは機能しないため、任意のグラフでダイクストラを常に安全に実行できるとは限りません。

ジョンソンのアルゴリズムと呼ばれる本当に注目に値するアルゴリズムがあります。これは、グラフに負のエッジが含まれている場合でも(負のサイクルがない限り)、各ノードからダイクストラのアルゴリズムを実行するためのわずかな変更です。このアルゴリズムは、最初にグラフ上でベルマンフォードを実行して負のエッジのないグラフに変換し、次に各頂点から開始するダイクストラのアルゴリズムを使用することで機能します。ベルマンフォードは時間O(mn)で実行されるため、全体的な漸近実行時間は依然としてO(mn + n 2 log n)です。したがって、m = o(n 2 )の場合(これはnの少し-oであることに注意してください)、アプローチは、Floyd-Warshallを使用するよりも漸近的に高速です。

ここでの1つの落とし穴は、これは、フィボナッチヒープに裏打ちされたダイクストラのアルゴリズムがあることを前提としていることです。使用可能なフィボナッチヒープがなく、ビルド、デバッグ、およびテストに必要な72時間を費やしたくない場合でも、ダイクストラのアルゴリズムにバイナリヒープを使用できます。実行時間をO(m log n)に増やすだけなので、このバージョンのJohnsonのアルゴリズムはO(mn log n)で実行されます。m =Ω( n2)の場合、Floyd-WarshallはO(n 3)で実行され、JohnsonのアルゴリズムはO(n 3 log n)で実行されるため、これはFloyd-Warshallよりも常に漸近的に高速であるとは限りません。ただし、m = o(n 2 / log n)であるスパースグラフの場合、Johnsonのアルゴリズムのこの実装は、Floyd-Warshallよりも漸近的に優れています。

要するに:

  • フィボナッチヒープを使用すると、ジョンソンのアルゴリズムは常に漸近的に少なくともフロイド-ワーシャルと同じくらい優れていますが、コーディングは困難です。
  • バイナリヒープを使用する場合、Johnsonのアルゴリズムは通常、少なくともFloyd-Warshallと同じくらい漸近的に優れていますが、大きくて密なグラフを処理する場合には適切なオプションではありません。

お役に立てれば!

于 2011-09-01T02:07:32.607 に答える
12

すべてのノードでダイクストラを実行するための複雑さは、O(EV + V 2 logV)になります。この複雑さは、 E <V 2の場合、O(V 3 )よりも低くなります。

于 2010-11-18T07:27:21.577 に答える
4

場合によります。すべてのノードに対してダイクストラを実行すると、が得られますがO(VE + V^2log V)、フロイドはO(V^3)です。の場合E = O(V^2)、2つは理論的に同一であり、実際にはフロイドの方が高速です。理論的にも実際的にも優れている場合はE = O(V)、すべてのノードに対してダイクストラを実行します。

基本的に、ノードとほぼ同じ数のエッジがあると予想される場合はすべてのノードからダイクストラを実行し、ほぼ完全なグラフがあると予想される場合はフロイドを実行します。

于 2010-11-18T14:08:27.090 に答える
-3

事実上、Floyd-Warshall は、すべてのペアの最短パスで Dijkstra のものよりも高速です (一般的に!!)

于 2012-07-11T18:58:57.347 に答える