3

ダイクストラ以外のほぼ完全なグラフの最短経路を計算する別の方法はありますか? 約 8,000 のノードと約 1,800 万のエッジがあります。私はスレッド「マップ上の a から b」を調べて、Dijkstra を使用することにしました。Boost::Graph ライブラリを使用して Perl でスクリプトを作成しました。しかし、結果は私が期待したものではありません。呼び出し $graph->dijkstra_shortest_path($start_node,$end_node); を使用して 1 つの最短パスを計算するのに約 10 分以上かかりました。

エッジがたくさんあることは理解していますが、それが実行時間が遅い理由かもしれません。私は水の中で死んでいますか？これを高速化する他の方法はありますか？

4

2 に答える 2

5

簡単な答え：いくつかの最短経路が必要な場合はダイクストラ法が最善の策であり、ノードのすべてのペア間の最短経路を見つけたい場合はFloyd-Warshallアルゴリズムの方が適しています。

  • ダイクストラのアルゴリズムは、重み付きグラフの場合、グラフ内の1つのソースから他のすべてのノードへの最短経路を見つけます。O（V ^ 2）時間で密グラフ上で動作します。

  • Floyd-Warshallは、ノードのすべてのペア間の最短経路を見つけます。密な表現が必要で、O（V ^ 3）時間で実行されます。加重グラフまたは非加重グラフで動作します。

グラフが密集している場合でも（質問のタイトルによると）、いくつかの最短経路を見つけたい場合は、グラフをスパースグラフに変換し、ダイクストラのスパース実装を使用することでメリットが得られる可能性があります。スパースダイクストラはO（E log V）で実行されます。

これは、すべてのエッジの重みが負ではないことを前提としていることに注意してください。もしそうなら、あなたはこれらのどれも使うことができません。Bellman-Fordのように、さらに遅いアルゴリズムを使用する必要があります。

于 2009-09-12T03:59:40.760 に答える
1

A* アルゴリズムを試してみることもできます。

このアプローチは、優れたヒューリスティックにアクセスできる場合に特に役立ちます。

于 2012-01-26T14:06:59.937 に答える