Dijkstra算法會進入死衚衕嗎？

Question

說我有如下圖：

  e (destination) 
      | 
      | (1) 
      | 
      d 
      | 
      | (100) 
      | 
    (start) a - - - b - - - c 
      (1)  (1) 

將Dijkstra算法運行鑽牛角尖？我想如果我從a開始，它會變成a-> b-> c並進入死衚衕，因此無法達到e。是這樣嗎？

Answer 1

顯然不是。從wikipedia description of Dijkstra's algorithm：

.3。對於當前節點，考慮所有未訪問的鄰居並計算它們的暫定距離。

這意味着，如果你開始在a，b和d都檢查（即他們的暫行距離計算），因爲它們未訪問過的鄰居。由於b具有較小的暫定距離，因此您可以訪問下一個。

如需更新，請使用附加節點e：如上所述，您的抵達地址爲c。但是你沒有被卡住 - 仍然有一個未預先確定的暫時距離的未訪問節點，即d - 所以你接下來訪問那個節點。