在Dijkstra算法的走访组的目的是什么？ [英] What is the purpose of the visited set in Dijkstra?

问题描述

在维基百科页面，Dijkstra算法，它们标志着访问节点，这样他们就不会再加入到队列中。然而，如果一个节点被访问然后可存在于该节点是短没有距离，所以不检查的alt＆其中; DIST [V] 已经占到访问节点？我误解一些关于访问组？

 的U形每个邻居五：
      ALT：= DIST [U] + dist_between（U，V）; //积累从源最短DIST
      如果ALT＆LT; DIST [V]＆安培;＆安培; ！参观[V]：
          DIST [V]：= ALT; //保持最短DIST从SRC到v
          previous [V]：= U;
          加入V.向Q; //添加未访问v转换成在Q被处理
      如果结束
  结束了
 

解决方案

是的，你说得对。没有必要对被访问的载体

如果一个节点被访问，那就不会存在该节点是较短的距离，所以，如你所说，检查 ALT＆LT; DIST [V] 就足够了。

看看这里：

On the Wikipedia page for Dijkstra's algorithm, they mark visited nodes so they wouldn't be added to the queue again. However, if a node is visited then there can be no distance to that node that is shorter, so doesn't the check alt < dist[v] already account for visited nodes? Am I misunderstanding something about the visited set?

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

解决方案

Yes, you're right. There's no need for the visited vector.

If a node is visited then there cannot exist a distance to that node that is shorter, so, as you said, checking alt < dist[v] is enough.

Take a look here:

这篇关于在Dijkstra算法的走访组的目的是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！