「それは素晴らしいアルゴリズムです」と彼は言った エリック・ディメイン、マサチューセッツ工科大学のコンピューター科学者。 「非常に速く、シンプルで、実装が簡単です。」
この手順を実践するには、メモを整理するためのシステム (コンピューター サイエンスの専門用語で言えばデータ構造) を決定する必要があります。それは些細な技術的な詳細のように聞こえるかもしれませんが、エントリを編集または削除する必要があるたびにメモを検索するのに費やす時間は、アルゴリズムの全体的な実行時間に大きな影響を与える可能性があります。
ダイクストラ氏の論文では、改善の余地が残された単純なデータ構造が使用されていました。その後数十年間、研究者たちは、愛情を込めて「ヒープ」と呼ばれる、特定のアイテムが他のアイテムよりも見つけやすい、より優れたアイテムを開発しました。これらは、ダイクストラのアルゴリズムが最も近い残りの頂点のエントリを削除するだけでよいという事実を利用します。 「ヒープは基本的に、これを非常に迅速に実行できるデータ構造です」と氏は述べた。 ヴァーツラフ・ロゾン、ブルガリアのソフィアにあるコンピューターサイエンス・人工知能・技術研究所（INSAIT）の研究者。
1984 年、2 人のコンピューター科学者が、 賢いヒープ設計 これにより、ダイクストラのアルゴリズムは、単一ソース最短経路問題を解くのに必要な時間の理論的限界、つまり「下限」に到達することができました。ある特定の意味では、このバージョンのダイクストラのアルゴリズムは可能な限り最高のものです。これは、40 年近くにわたってこの問題の標準バージョンに関する最後の言葉でした。状況が変わったのは、数人の研究者が「最高」とは何を意味するのかを詳しく調べたときだけでした。
最良の行動
研究者は通常、最悪のシナリオでアルゴリズムがどのように機能するかを研究することでアルゴリズムを比較します。世界で最も複雑な道路網を想像して、特に複雑な交通パターンをいくつか加えてみましょう。このような極端な状況で最速のルートを見つけたい場合は、1984 年バージョンのダイクストラのアルゴリズムが無敵であることが証明されています。
しかし、願わくば、あなたの街が世界で最悪の市街路網を持っていないことを願っています。そこで、「あらゆる道路網において無敵のアルゴリズムは存在するのでしょうか?」と疑問に思うかもしれません。この質問に答えるための最初のステップは、各ネットワークには最悪のトラフィック パターンがあるという保守的な仮定を立てることです。次に、考えられる最悪の重みを想定して、アルゴリズムが考えられるグラフ レイアウトを通じて最速のパスを見つけられるようにする必要があります。研究者はこの状態を「普遍的最適性」と呼んでいます。グラフ上のある点から別の点に移動するという単純な問題に対して普遍的に最適なアルゴリズムがあれば、世界中のすべての都市でラッシュアワーの交通を克服するのに役立つ可能性があります。
