ダイクストラのアルゴリズム


n 個の頂点と m 個の辺を持つ有向または無向の重み付きグラフを指定します。すべてのエッジの重みは負ではありません。いくつかの開始頂点 s が指定されています。頂点 から他のすべての頂点までの最短パスの長さを見つけ、最短パスそのものを出力する方法も提供する必要があります。
 
この問題は「単一ソース最短経路問題」と呼ばれます。 (単一ソース最短経路問題)。

1-K BFS と同じタスクを実行しますが、K は関係ありません。また、1-K BFS と同様に、負のエッジを適切に処理しません。

アルゴリズム:
ダイクストラのアルゴリズム自体は N 回の反復で構成されます。次の反復では、頂点 V まだマークされていない頂点のうち、その頂点までの距離が最も小さい場合、この頂点がマークされ、そこから隣接する頂点の緩和が発生します。


 アルゴリズムの最終的な漸近動作は次のとおりです: O(n2+ m)

Training problem

ダイクストラ: 始まり (C++)

Training problem

ダイクストラ

ダイクストラのアルゴリズムの単純な実装の漸近動作は次のとおりであるため、\(O(n^2 + m)\) となり、頂点の数が増加すると、次のようになります。仕事のスピードが物足りなくなって
しまいます。 改善のためにさまざまなデータ構造を使用できます: フィボナッチ ヒープ、セット セット、または優先キューpriority_queue.
set を使用した例を考えてみましょう。その結果、最終的な漸近線は次のようになります。\(O(n log (m))\) 、詳細。

Training problem

O(M logN) c set のダイクストラのアルゴリズム: 開始 (C++)