陷入Dijkstra算法

Getting stuck on Djikstra Algorithm

我正在尝试将 Djikstra 算法应用到教科书上的这张图上，但在尝试从 G->C 遍历时，我一直卡在顶点 A 上。这是图形图像的 link： LINK

我将在下面概述我的步骤：

  1. 我从初始顶点（G）开始。

  2. A 的成本为 6，E 的成本为 1，H 的成本为 4，因为它们最初都是无穷大。 G 被标记为已访问。

  3. 我去找花费最少的邻居；在这种情况下，它的 E.

  4. 在E处，我把B的cost设置为1+2=3，F的cost设置为1+2=3，然后把E标记为visited

  5. 我以最低的成本访问了 E 的邻居：这是我开始卡住的地方，因为 B 和 F 的成本相同。 假设我选择 B。
  6. 在B处，我设C的成本为3 + 7 = 10，A的成本为5。
  7. 现在 A 是成本最低的邻居，但是访问它让我卡住了，因为我无法出去。

如果我处理错误，我将不胜感激一些建议或更正。

由于 G 已被标记为已访问，因此不再考虑此节点，因此也考虑 A，因为没有更多可能的连接。

在第6步中访问过的节点是G,E,B。现在你必须选择最小距离值的节点，也就是F。所以第 7 步中的缺陷实际上是假设它必须是邻居节点。

从第 7 步继续：

  1. 选择 F。将 C 的距离更新为 6。标记 F 已访问。
  2. 选择 H。将 D 的距离更新为 6。标记 H 已访问。
  3. 现在选择 A。无需更新。标记 A 访问过。
  4. 按任意顺序选择 C ​​或 D，并将它们也标记为已访问。此处无需更新。