algorithm - 我们真的需要 Dijkstra 算法中顶点的 "visited or not"信息吗？

Question

在Dijkstra's algorithm on Wikipedia (older version, now corrected by me) ，优先队列的实现会在检查较短的路径之前检查顶点是否被访问。

真的有必要吗？甚至是正确的？

function Dijkstra(Graph, source):
      dist[source] ← 0                      // Initialization
      for each vertex v in Graph:           
          if v ≠ source
              dist[v] ← infinity            // Unknown distance from source to v
              prev[v] ← undefined           // Predecessor of v
          end if
          Q.add_with_priority(v,dist[v])
      end for 


     while Q is not empty:               // The main loop
         u ← Q.extract_min()               // Remove and return best vertex
         mark u as scanned
         for each neighbor v of u:
             if v is not yet scanned: // **is this in need?**
                 alt = dist[u] + length(u, v) 
                 if alt < dist[v]
                     dist[v] ← alt
                     prev[v] ← u
                     Q.decrease_priority(v,alt)
                 end if
             end if
         end for
     end while
     return prev[]

我认为如果 v 的路径需要更新，检查 v 是否已经被扫描 将防止将来出现任何机会。

---

更新:

我编辑了页面和 current Dijkstra's algorithm wiki page现在是正确的。

Answer 1

不需要标志。看看这段伪代码:

if v is not yet scanned:
    alt = dist[u] + length(u, v) 
    if alt < dist[v]
         dist[v] ← alt
         prev[v] ← u
         Q.decrease_priority(v,alt)
    end if
end if

如果你检查不同的部分:

• alt似乎是一个局部变量，在这里仅用作临时变量，因此写入它在其他任何地方都没有任何区别。
• 如果v已经从队列中删除，它的路径至多与 u 的路径一样长, 否则 u会先被提取出来。
• 如果v被访问，然后dist[v] <= dist[u] <= alt .在那种情况下比较alt < dist[v]是假的，其余的代码无论如何都会被跳过。

再多解释一下，想想优先级队列的作用。它包含节点，按到达它们的最短已知路径 排序。当从队列中提取一个节点时，之前的所有节点最多与该节点一样远，之后的所有节点至少与该节点一样远。由于所有较近的节点都已处理，因此发现到这些节点之一的任何新路径都将通过至少同样远的节点。这意味着从仍在队列中的节点到提取节点的任何更短路径，因此仅检查 alt < dist[v]将已经排除那些被扫描的节点。