algorithm - Dijkstra 中访问集的目的是什么？

Question

在 Dijkstra 算法的维基百科页面上，他们标记了访问过的节点，这样它们就不会被再次添加到队列中。然而，如果访问了一个节点，那么到那个更短的节点就没有距离了，所以不检查 alt < dist[v]。已经考虑访问过的节点？我对访问集有什么误解吗？

for each neighbor v of u:   
      alt := dist[u] + dist_between(u, v);          // accumulate shortest dist from source
      if alt < dist[v] && !visited[v]:                                 
          dist[v]  := alt;                          // keep the shortest dist from src to v
          previous[v]  := u;
          insert v into Q;                          // Add unvisited v into the Q to be processed
      end if
  end for

Answer 1

实际上有两套你需要考虑:

• 访问集
• 排队集合

访问集

已访问集包含那些已从排队集中弹出的顶点。这些不能重新访问，因为根据定义，已经发现了从起点到这些顶点的最短路径

排队集合

排队的集合包含未探索的顶点，这些顶点按照最短距离到起始顶点的顺序排队。此队列通常使用 (min) heap 表示结构。

---

解释

取决于density在图中，每个顶点都有可能成为多个边的一部分。 请注意，边是将一个顶点连接到另一个顶点的最小组件。因此，这意味着可能有多个顶点与当前顶点有一条边。

Dijkstra's algorithm 外循环的每次迭代取与起始顶点距离最小的顶点(来自排队的集合)，并放宽连接到它的每个顶点的边成本。如果顶点已经在队列集中，则更新队列中的值和位置。

原因alt < dist[v]完成是因为有可能多次遇到一个已经在队列中的顶点，所以每次遇到它时，您都必须确保在编辑它到源顶点的距离之前，它的当前距离大于新的距离你想分配给它的距离 ( alt < dist[v] ) 并且它没有像访问过的那样处理 ( !visited[v] )

最短距离

• Dijkstra 算法根据定义提供保证，一旦节点被标记为 visited ，该节点到源的距离值最短。 如果一个节点被标记为已访问，这并不意味着与从源到任何其他节点的距离相比，从该节点到源的距离是最短的距离。 Visited 意味着 Dijkstra 算法的目标已经满足该节点；即它当前存储从源到自身的最小距离。

• 如果您完全想放弃对已访问的检查，那么您可以做的是，一旦将节点标记为已访问，就遍历连接到该节点的所有边并删除他们。这确保任何 future 处理的节点，没有连接到任何标记为已访问的节点的边缘。但是，因为该图是使用 adjacency list 表示的, 使用此选项会花费大量时间；根据图的密度，你最好只拥有一个访问集。
  如果您使用 adjacency matrix 表示图表，那么这样做的好处是支票只会花费 O(N)时间。但是，邻接矩阵使用 N² 空间与邻接列表的 N 空间相比，您将为此在内存中付出代价，这可能或根据图形大小，可能不会那么糟糕。

最后

一旦理解了所有这些，您就会发现代码中所做的一切都是产生正确结果所必需的。