1

Dijkstra のアルゴリズムの実行時の複雑さについて質問があります。(CLRS バージョン 3 の疑似コードを参照):

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← ∅ 
3 Q ← V[G]
4 while Q != ∅ 
5   do u ← EXTRACT-MIN(Q)
6   S ← S ∪ {u} 
7   for each vertex v ∈ Adj[u]
8     do RELAX(u, v,w)

行 3 は O(V)、行 5 は合計で O(VlogV) であると理解しています。行 7 は合計で O(E) であり、行 8 は reduce_key() を意味するため、Relax() 操作ごとに logV です。しかし、relax() では、d[v]>d[u]+weight となり、緩和することを決定した後、recrease_key(Q, pos, d[v] を呼び出す前に、キュー Q 内の v の位置を調べるべきではありませんか? ) pos のキーを d[v] に置き換えるには? このルックアップ自体に O(V) のコストがかかることに注意してください。したがって、各 Relax() は、O(logV) ではなく O(V) のコストがかかるはずですよね?

スペースの複雑さに関する質問: キュー Q の頂点を比較するには、距離を 1 つのメンバーとして構造体/クラスの頂点を設計し、距離を比較して頂点を並べ替える operator< などを実装します。しかし、Relax() で dist[v] = dist[u]+weight を実行するには、複製配列 dist[] を定義する必要があるようです。複製配列を定義しない場合、キュー Q で v と u の位置を検索し、それらの距離を取得して確認する必要があります。このように動作すると思われますか？それとも私の実装が良くないのですか？

4

1 に答える 1

5

ダイクストラのアルゴリズム（あなたが書いたように）には、データ構造を指定しない限り、実行時の複雑さはありません。「7 行目」が O(E) 操作を説明していると言っているのはどういうわけか正しいですが、行を見ていきましょう (幸いなことに、ダイクストラは「簡単に」分析できます)。

  1. 初期化とは、「距離が 0 のソースを除いて、すべての頂点に無限の距離を与えることを意味します。非常に簡単に、これは O(V) で実行できます。

  2. セット S は何に適していますか? 「書き込み専用」で使用します。

  3. すべての要素をキューに入れます。ここにドラゴンがいます。(優先!) キューとは何ですか? add、オプションで reduceKey (Dijkstra に必要)、remove (Dijkstra では不要)、extractMin 操作を含むデータ構造。実装に応じて、これらの操作には特定のランタイムがあります。たとえば、単なる (マーキング) セットであるダム PQ を作成できます。キーの追加と削除は一定時間ですが、最小値を抽出するには検索する必要があります。Dijkstra での標準的な解決策は、関連するすべての操作を O(log n) で実装するキュー (ヒープなど) を使用することです。技術的に言えば、フィボナッチ ヒープの方が優れていますが、このケースを分析してみましょう。自分でキューを実装しないでください。実際の PQ 実装を使用してどれだけ節約できるかは驚くべきことです。

  4. ループを n 回実行します。

  5. 毎回、O(n log n) 合計 (すべての反復にわたって) にある最小値を抽出します。

  6. セット S は何に適していますか?

  7. 各頂点のエッジを通過するのは最大で 1 回です。つまり、各エッジを最大で 2 回タフにするので、ループ内で発生することはすべて O(E) 回実行します。

  8. リラックスとは、キーを減らす必要があるかどうかを確認して、そうするということです。そのような操作のそれぞれが (ヒープの場合) キューに O(log V) を追加できることは既にわかっており、O(E) 回実行する必要があるため、S O(E log V) となり、合計ランタイムを支配します。 .

フィボナッチ ヒープを取ると、O(VlogV+E) まで下げることができますが、それはアカデミックです。実際の実装ではヒープを調整します。実装のパフォーマンスを知りたい場合は、PQ 操作を分析してください。しかし、私が言ったように、何をしているのか正確にわからない場合は、既存の実装を使用することをお勧めします。「reduceKeyを呼び出す前に位置を調べる」というあなたの考えは、挿入ごとに効果的にO(V)を取る実装を考え出す前に、そのトピックをより深く掘り下げる必要があることを教えてくれます(reduceKeyが呼び出されるたびにソートすることにより)またはO( V) extractMin ごと (オンデマンドで最小値を見つけることにより)。

于 2013-05-16T07:06:28.757 に答える