graph-theory - ダイクストラよりも高速なアルゴリズムはありますか？

Question

正のエッジ重みのみを持つ有向連結グラフを考えると、フィボナッチヒープを使用するダイクストラよりも、2つの頂点間の最短経路を見つけるためのより高速なアルゴリズムはありますか？

ウィキペディアによると、ダイクストラはO（| E | + | V | * log（| V |））にあります（フィボナッチヒープを使用）。

たとえば、実行時間の半分の最適化ではなく、時間計算量が異なるアルゴリズム（O（n * log n）からO（n）への移行など）を探しています。

さらに、以下のアプローチについてのご意見をお聞かせください。

1. すべてのエッジの重みのGCDを決定します。
2. グラフを均一なエッジの重みを持つグラフに変換します。
3. BFSを使用して、指定された2つの頂点間の最短経路を見つけます。

ポイント2の例：
GCDが1であると想像してください。次に、エッジ
A ---> B（エッジの重み3）
を
A-> A'-> A''-> B（エッジの重み1の3倍）に変換します。
この変換には一定の時間がかかり、エッジごとに1回実行する必要があります。したがって、このアルゴリズムはO（| E |）（変換）+ O（| E | + | V |）（BFS）= O（2 * | E | + | V |）= O（| E | + | V |）

私の質問を読むために時間を割いてくれてありがとう、そして私はあなたの時間を無駄にしないことを望みます^^。良い１日を。

Answer 1

あなたがあなたのアルゴリズムのために行った大きなああ分析はひどく欠陥があります。すべての辺が素数であると仮定します。新しいグラフのエッジの数は、すべての重みの合計に等しくなります。したがってO(|E| + |V|)、新しいグラフは実際O(W x |E| + |V|)には元のグラフにあり、。よりもはるかに大きくなる可能性がありますO(|E| + |V| log |V|)。

Answer 2

ダイクストラよりも高速なアルゴリズムはありますか?

はい。すべての場合、またはほとんどの場合でさえ、より良いパフォーマンスを要求するように、質問は限定されていません。肯定的な答えを確立するには、1 つのケースでより優れたパフォーマンスを発揮するアルゴリズムで十分です。

ダイクストラ法よりもベルマンフォード法が必要とする反復回数が一般的に多いにもかかわらず、実際には、反復ごとのオーバーヘッドが小さいため、ベルマンフォード法の方が優れている可能性があります [Golden, B., 1976.「Shortest-Path Algorithms: A比較」、Operations Research、Vol。44、pp。1164-1168]。

上記の引用は、Dimitri P. Bertsekas (1992 年 3 月) からのものです。「最短パスのためのシンプルで高速なラベル修正アルゴリズム」(PDF)。ネットワーク、Ｖｏｌ．23, pp. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf . 2008 年 10 月 1 日閲覧。

要するに、私の主張はベルツェカスのゴールデンの解釈に基づいている。私の結論が正しいかどうかは別として、Bertsekas がダイクストラ アルゴリズムをラベル設定方法として分類し、ラベル修正方法と対比することに興味を持っていることに気付くかもしれません。

Answer 3

O(1) を持つアルゴリズムがあります。重みをチェーンの長さに変換し、ノードにキー リングを使用します (ポケットにあるような実際のキー リング)。キーホルダーを正しいチェーンに接続します。2 つのノードを選択し、互いに引き離します。

あるノードから別のノードへの張ったチェーンに従ってください。これが最短経路です。

これをコンピュータ プログラムとして実装するには、2 台の産業用ロボットが必要です :)

より現実的な例として、Ant コロニーの最適化を使用すると、短時間で非常に良い結果が得られます。このアルゴリズムでは実行回数を指定できるため、O(n) が得られますが、完璧な結果が保証されるわけではありません。

Answer 4

常に A* があり、それは Hierarchical A* や A* JPS のような派生物です。