Dijkstra 具有正权重和循环的有向图算法

Question

如果我有一个带有循环且只有正权重的有向图，并且不使用优先级队列，而是使用队列并不断添加所有子项，包括那些因为我选择不跟踪已访问而被访问过的子项，我的算法会落下吗无限循环？我无法对此产生直觉，也不确定我的理解是否正确。

Answer 1

为此请考虑下图：

并考虑伪代码，而不跟踪访问的节点。

 1  function Dijkstra(Graph, source):
  2      
  3      for each vertex v in Graph.Vertices:
  4          dist[v] ← INFINITY
  5          prev[v] ← UNDEFINED
  6          add v to Q
  7      dist[source] ← 0
  8      
  9      while Q is not empty:
 10          u ← Q.pop()
 11          remove u from Q
 12          
 13          for each neighbor v of u still in Q:
 14              alt ← dist[u] + Graph.Edges(u, v)
 15              if alt < dist[v]:
 16                  dist[v] ← alt
 17                  prev[v] ← u
 18                  add v to Q
 19
 20      return dist[], prev[]

我们知道有一个环，并假设边的权重大于零。通过该算法，我们知道最多 2 步后，我们就处于从 B 开始的循环中。扫描其邻居 C，更新其距离并再次添加其邻居。这样做直到当前节点是E。此时，我们知道到E的距离小于无穷大，并且队列中有D和F。我们再次更新 F 的距离，添加其邻居（为空）并更新 D 的距离。如果我们再次将 D 的邻居添加到队列中，则队列中有 B。在第 18 行中，我们可以看到，如果前一个节点的距离小于 B 的当前距离，我们只是将节点添加到队列中。因为，我们只有大于 0 的边权重，所以距离不可能D 的距离小于 B 的距离。因此，我们不会向队列中添加任何其他节点，这会将队列留空。如果队列为空，算法将终止。如果我们，例如稍微修改一下算法，s.t.我们始终是队列的邻居，是的，可能存在算法不会终止的情况。但这只是情况，如果我们不检查距离是否更小或不跟踪访问的节点。

长话短说：

如果你有东西来跟踪程序的当前状态，让它成为节点的距离或访问了哪个节点等，你就不会遇到任何无限循环。