Djikstraのアルゴリズム：隣人や子供を繰り返していますか？

Question

私はウィキペディア

1 function Dijkstra(Graph, source): 
2 
3  create vertex set Q 
4 
5  for each vertex v in Graph:    // Initialization 
6   dist[v] ← INFINITY     // Unknown distance from source to v 
7   prev[v] ← UNDEFINED     // Previous node in optimal path from source 
8   add v to Q       // All nodes initially in Q (unvisited nodes) 
9 
10  dist[source] ← 0      // Distance from source to source 
11  
12  while Q is not empty: 
13   u ← vertex in Q with min dist[u] // Source node will be selected first 
14   remove u from Q 
15   
16   for each neighbor v of u:   // where v is still in Q. 
17    alt ← dist[u] + length(u, v) 
18    if alt < dist[v]:    // A shorter path to v has been found 
19     dist[v] ← alt 
20     prev[v] ← u 
21 
22  return dist[], prev[] 

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

上の擬似コードでDjikstraのアルゴリズムで探していて、私を混乱だ部分がライン16です。 for each neighborと記載されていますが、それはfor each child（つまりfor each neighbor where neighbor != parent）であるべきではありません。さもなければ、私は親を20の行に設定する点を見ません。

Answer 1

前のノードがライン20に設定されている：

prev[v] ← u 

ライン14が実行された場合にのみ発生します

remove u from Q 

ので、任意のvため、prev[v]はQにすることはできません - それは以前は削除されていて、Qには戻ってこない（12から始まるループ内では、項目はもうQに追加されません）。これは、いずれもu、prev[u]にはありませんと言っているのと同じですQに - 変数の名前を変更することから、それは同じことを言います。

それはあなたが擬似コードを見れば、それが実際に

for each neighbor v of u:   // where v is still in Q. 

を言い、 for each neighbor

を言うしかし：あなたはライン16の周りと言う質問には

---

したがって、prev[u]は繰り返されません.012にはありません。何が価値があるために

---

、私は擬似コードは// where v is still in Qはコメントすべきではない少しずさんと混乱だと思います。コードの残りの部分を明確にしたり説明したりすることはありません。意味を変更し、のの部分にする必要があります。おそらくそれはあなたを混乱させました。

Answer 2

最終的にDijkstraのアルゴリズムは、​​と呼ばれるものを計算します。ツリー内のパスがグラフの各ノードへの最短経路を与える開始ノードをルートとするツリー構造です。それぞれのノードの親を設定するロジックは、一度に1つのノードをツリーを構築するDijkstraのアルゴリズムの一部です。

ダイクストラのアルゴリズムは、最短パスのツリーであるをビルドしていますが、その上を歩いていません。むしろ、元の経路のノードを特定の順序で処理し、処理されたノードに隣接するノードの候補距離を絶えず更新することによって機能する。つまり、擬似コードでは、「すべての隣接ノードをループする」という論理は、「隣接するすべてのノードをループして元のグラフにをループする」ことを意味するため正しいです。 "すべての子に対して繰り返し処理することはできません生成された最短経路木のノードは、そのツリーがアルゴリズムのその時点で完全に組み立てられていないためです。