algorithm - ダイクストラのアルゴリズムが最高の単一ソース最短経路アルゴリズムであることをどのように知ることができますか?

Question

ダイクストラのアルゴリズムがどのように機能するか、また O(m + n log n) 時間で実行できることを知っています。これよりも優れた単一ソースの最短パスのアルゴリズムがないことをどうやって知ることができますか?

Answer 1

ダイクストラのアルゴリズムは、実際には、グラフ内の単一ソースの最短パスを計算するための最速のアルゴリズムであるとは限りません。たとえば、すべてのエッジが整数の重みを持つことがわかっていて、機械語がそれらの整数のいずれかを保持するのに十分な大きさであると仮定すると、時間 O(m + n) で実行される Thorup によって開発されたアルゴリズムを使用できます。ダイクストラのアルゴリズムよりも漸近的に高速です。エッジが重み付けされていない場合、またはそれらがすべて同じ重みを持っている場合、単純な BFS は時間 O(m + n) でこれを行います。