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

Question

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

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

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 is scanned already or not 会阻止任何机会。

更新：

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

Answer 1

需要检查V是否已经被扫描

在第一个循环中，我们找到顶点(V1)，它是源顶点(S1) 的相邻顶点的最小成本。

在第二个循环中，我们不应该从顶点(V1)反转回源顶点(S1)。

当长度(S1,V1) 是相邻成本顶点(V1) 的最小值时，反向回到源顶点(S1)。

不检查是否扫描V的代码在某些情况下会导致循环。

Answer 2

不需要旗帜。看看这段伪代码：

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] 已经排除了那些被扫描的节点。

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

Do we really need the "visited or not" info of a vertex in Dijkstra's algorithm?

algorithm

graph

dijkstra

shortest-path

data-structures