他の人が指摘しているように、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と同じくらい漸近的に優れていますが、大きくて密なグラフを処理する場合には適切なオプションではありません。
お役に立てれば!