algorithm - Dijkstra 算法会陷入死胡同吗？

Question

假设我有以下图表：

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

Dijkstra 的算法会陷入死胡同吗？我想如果我从a开始，它会去a->b->c并进入死胡同，因此无法到达e。是这样吗？

Answer 1

显然不是。来自Dijkstra 算法的维基百科描述：

.3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。

这意味着如果您从 开始a，b并且d都被检查（即计算它们的暂定距离），因为它们是未访问的邻居。因为b有较小的暂定距离，你下一个访问那个。

对于您使用额外节点的更新：您如上所述e到达。c但是您并没有被卡住 - 仍然有一个未访问的节点具有预先计算的暂定距离，即d- 所以您接下来访问那个节点。