17

在 Dijkstra 算法的 Wikipedia 页面上，它们标记了访问过的节点，这样它们就不会再次被添加到队列中。但是，如果访问了一个节点，那么到该节点的距离就不会更短，那么检查不是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
4

3 回答 3

13

你是对的。不需要访问的向量。

如果访问了一个节点，则到该节点的距离不能更短，因此，正如您所说，检查alt < dist[v]就足够了。

看看这里：

于 2013-11-13T14:56:43.623 回答
12

实际上有2套你需要考虑：

  • 访问集
  • 排队的集合

访问集

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

排队的集合

排队的集合包含未探索的顶点，按照与起始顶点的最短距离的顺序排列。此队列通常使用 [min]堆结构表示。

解释

根据图的密度，每个顶点都有可能成为多条边的一部分。请注意，边是将顶点连接到另一个顶点的最小组件。因此，这意味着有多个顶点与当前顶点有边的可能性。

Dijkstra 算法的外循环的每次迭代都采用与起始顶点距离最小的顶点（来自排队集合），并放宽与其连接的每个顶点的边成本。如果顶点已经在队列集中，它的值和队列中的位置被更新。

这样做的原因alt < dist[v]是因为有可能多次遇到已经在队列中的顶点，所以每次遇到它时，您必须确保在编辑它与源顶点的距离之前，它的当前距离大于您要分配给它的新距离 ( alt < dist[v]) 并且它不会被处理为已访问 ( !visited[v])

最短距离

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

  • 如果您完全想放弃对visited的检查，那么您可以做的是，一旦将节点标记为已访问，就遍历连接到该节点的所有边并删除它们。这确保任何未来处理的节点都没有连接到任何标记为已访问节点的边。但是，由于图形是使用邻接表来表示的，因此使用此选项会耗费大量时间；并且根据图表的密集程度，您最好只拥有一个访问集。
    如果您使用邻接矩阵来表示您的图，那么这样做的好处是检查只会花费O(N)时间。然而，邻接矩阵使用N 2空间 vsN个邻接列表空间，您将为此在内存中付出代价，这可能会或可能不会那么糟糕，具体取决于图形大小。

最后

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

于 2013-11-10T20:19:11.973 回答
-1

如果我们遇到负循环，可能会发生 alt < dist[v] 对于已经访问过的节点会变为 true 。但是我们不必考虑负循环，因此检查节点是否已被访问很重要。

于 2021-10-17T19:58:02.513 回答