具有正權重和回圈的有向圖Dijkstra演算法-有解無憂

如果我有一個帶有回圈且只有正權重的有向圖，而不是使用優先佇列，而是使用佇列并繼續添加所有子節點，包括那些因為我選擇不跟蹤訪問者而被訪問的子節點，我的演算法是否會落入無限回圈？我無法對此產生直覺，也不確定我的理解是否正確。

uj5u.com熱心網友回復：

為此，請考慮下圖：

具有正權重和回圈的有向圖 Dijkstra 演算法

并考慮偽代碼，而不跟蹤訪問過的節點。

 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 的距離。因此，我們不會向佇列中添加任何其他節點，這將使其為空。如果佇列為空，演算法將終止。如果我們，例如稍微修改演算法，我們總是它的鄰居到佇列，是的，可能存在演算法不會終止的情況。但這只是這種情況，如果我們不檢查距離是否更小或不跟蹤訪問過的節點。

長話短說：

如果您有一些東西要跟蹤程序的當前狀態，讓它成為節點的距離或訪問了哪個節點等，您將不會遇到任何無限回圈。除非邊權重為負。

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505882.html

標籤：算法数据结构迪杰斯特拉有向无环图循环图

上一篇：在漸近符號中，為什么我們不使用所有可能的函式來描述函式的增長率？

下一篇：使用二進制數列確定哪些框被填充