algorithm - Dijkstra的算法:我要遍历邻居还是 child ？

我在看维基百科上的伪代码中的djikstra算法

 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
让我困惑的是line16。上面写着，但不应该是否则我看不到在for each neighbor行中设置父对象的意义。

最佳答案

前一个节点设置在第20行：

prev[v] ← u

只有在执行第14行时才会发生这种情况：

remove u from Q

因此，对于任何v，prev[v]都不能在Q中-它以前被删除过，并且永远不会返回到Q（在从12开始的循环中，不再向Q添加项）。这与对于任何u，prev[u]不能在Q-asides中更改变量名的说法是一样的。
在这个问题上，关于第16行：
上面写着for each neighbor
但是，如果你看一下伪代码，它实际上说

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

因此，prev[u]不会被迭代-它不在Q中。
值得一提的是，我认为伪代码有点草率，不应该是注释。它不会澄清或解释代码的其余部分-它改变了含义，应该是代码的一部分也许这让你困惑。

关于algorithm - Dijkstra的算法:我要遍历邻居还是 child ？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39899483/