algorithm - 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. For the current node, consider all of its unvisited neighbors and calculate their tentative distances.

这意味着，如果您从 a 开始，b 和 d 都会被检查(即计算它们的暂定距离)，因为它们是没有拜访过的邻居。由于 b 的暂定距离较小，因此您接下来访问该距离。

对于使用额外节点 e 进行的更新:您将到达 c，如上所述。但您并没有陷入困境 - 仍然有一个未访问的节点，其具有预先计算的暂定距离，即 d - 因此您接下来访问该节点。