DijkstraとPrimのアルゴリズム

Question

DijkstraとPrimのアルゴリズムは同じです。ウィキペディアの擬似コードはここにあります。私は私の混乱のポイントを説明します。

1 function Dijkstra(Graph, source): 
2  dist[source] ← 0         // Initialization 
3 
4  create vertex set Q 
5 
6  for each vertex v in Graph:   
7   if v ≠ source 
8    dist[v] ← INFINITY       // Unknown distance from source to v 
9    prev[v] ← UNDEFINED       // Predecessor of v 
10 
11   Q.add_with_priority(v, dist[v]) 
12 
13 
14  while Q is not empty:        // The main loop 
15   u ← Q.extract_min()       // Remove and return best vertex 
16   for each neighbor v of u:      // only v that is still in Q 
17    alt ← dist[u] + length(u, v) 
18    if alt < dist[v] 
19     dist[v] ← alt 
20     prev[v] ← u 
21     Q.decrease_priority(v, alt) 
22 
23  return dist[], prev[] 

プリム法ではほぼ同じ、便宜のために、私はちょうど14行目で開始したループを変更します

14  while Q is not empty:        
15   u ← Q.extract_min()        
16   for each neighbor v of u:      
17    if v ∈ Q and length(u, v) < cost[v] 
18     cost[v] ← length(u, v) 
19     prev[v] ← u 
20     Q.decrease_priority(v, length(u, v)) 

2つの変更が最初はcost[]となどとdist[]を交換され、ありますアルゴリズムがさまざまな問題を解決するという事実に関連していると私は理解しています。 2番目のものはわたしにとってはあいまいです。すなわち、ダイクストラのアルゴリズムでは、この条件がないのがif v ∈ Qです。私は実際にプリムのアルゴリズムで訪れた頂点の集合に戻ることができない理由を実際には得ていません。これはダイクストラのアルゴリズムでは起こり得ません。

Answer 1

でV" を、私たちはalt ← dist[u] + length(u, v)を計算し、 が現在の値dist[v]より小さい場合、10〜altになります。 altは、uを経由すると、開始ノードからvまでの距離を表します。しかし、uは、ちょうどQから取り出されたノードであるため、開始ノードからの距離は、以前に取り出された他のすべてのノードよりも大きいか等しい。Q。ダイクストラが非負であることがすべてのエッジの重みを必要とするので、それはdist[u]とlength(u, v)の和であり、そしてそれはif状態を通過しないのでvがQにない場合、altは以上dist[v]に等しくなることが保証されます。つまり、vがQに含まれていない場合、vに既にあるパスに対して、uが迂回することになります。

Answer 2

あなたの考えが正しいかどうかわかりません。 Dijkstraアルゴリズムとprimsアルゴリズムの両方で、私たちはQの頂点のみを扱うべきです。 Dijkstraアルゴリズムの場合、擬似コードは現在の頂点が依然としてQ内にあるかどうかを明示的にチェックすることはできませんが、 Q」私は、彼らはXと同じことを意味想定し

for each neighbor v of u:      // only v that is still in Q 

∈Q

17    if x ∈ Q and length(u, v) < cost[v] 

ここで、xが表す場合は "ダイクストラではライン16

Answer 3

ダイクストラとプリムのアルゴリズムは非常に似ています。

違いがある：

• プリム法：無向エッジを介して最小スパニングツリーに最も近い頂点

• Dijsktraのアルゴリズム：有向パスを介してソースに最も近い頂点

出典：Sedgewickによるアルゴリズム&ウェイン