[解決済み] Dijkstraのアルゴリズムはなぜdecrease-keyを使うのですか？

質問

Dijkstraのアルゴリズムを教わったが、以下のようなものだった。

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

しかし、私はこのアルゴリズムに関していくつか読みましたが、私が見た多くのバージョンは、挿入とは対照的に、キーを減少させることを使用しています。

これはなぜでしょうか、また、この2つのアプローチの違いは何でしょうか？

どのように解決するのですか？

ノードの再挿入ではなくdecrease-keyを使用する理由は、優先キュー内のノード数を小さくすることで、優先キューのデキューの総数を小さくし、各優先キューバランスのコストを低く保つためです。

ノードを新しい優先度で優先度キューに再挿入するダイクストラアルゴリズムの実装では、グラフ内のm個のエッジごとに1つのノードが優先度キューに追加されます。 これは、優先度キューに対するm回のenqueue操作とm回のdequeue操作があることを意味し、総実行時間はO(m T _e + m T _d ), ここで T _e は優先キューへの入庫に要する時間であり、T _d は優先キューからデキューするために必要な時間である。

decrease-keyをサポートするDijkstraアルゴリズムの実装では、ノードを保持する優先キューはn個のノードで始まり、アルゴリズムの各ステップで1個のノードが削除されます。 これは、ヒープデキューの総数がnであることを意味します。各ノードは、それにつながる各エッジに対して潜在的に一度だけdecrease-keyが呼ばれるので、行われるdecrease-keyの総数は最大でmとなります。 _e + n T _d + m T _k ), ここで T _k はdecrease-keyを呼び出すのに必要な時間です。

では、これはランタイムにどのような影響を与えるのでしょうか？ それは、使用する優先順位キューに依存します。 ここに、異なる優先順位キューと、異なるダイクストラアルゴリズムの実装の全体的な実行時間を示す簡単な表があります。

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

ご覧のように、ほとんどの種類の優先度キューでは、漸近的な実行時間に差はなく、decrease-keyバージョンはあまり良い結果をもたらさないようです。 しかし、もしあなたが フィボナッチヒープ の実装を使用する場合、確かにDijkstraのアルゴリズムは、decrease-keyを使用する場合、漸近的に効率的となります。

要するに、decrease-keyを使用し、さらに優れた優先キューを使用することで、Dijkstraの漸近的実行時間を、エンキューとデキューをやり続ける場合に可能なものよりも低下させることができるのです。

この点以外にも、Gabowの最短経路アルゴリズムのような、より高度なアルゴリズムでは、ダイクストラのアルゴリズムをサブルーチンとして使用し、減少キーの実装に大きく依存しています。 彼らは、有効な距離の範囲を事前に知っていれば、その事実に基づいて超効率的な優先キューを構築できるという事実を利用しています。

これが役に立つといいのですが!