我正尝试将 Djikstra 算法应用于教科书中的这张图,但在尝试从 G->C 遍历时,我一直卡在顶点 A 上。这是图形图像的链接: LINK
我将在下面概述我的步骤:
我从初始顶点 (G) 开始。
A 的成本为 6,E 的成本为 1,H 的成本为 4,因为它们最初都是无穷大。 G 被标记为已访问。
我去找成本最低的邻居;在本例中是 E。
在 E 处,我将 B 的成本设置为 1 + 2 = 3,将 F 的成本设置为 1 + 2 = 3。然后将 E 标记为已访问。
- 我以最低的成本访问了 E 的邻居:这是我开始卡住的地方,因为 B 和 F 的成本相同。假设我选择 B。
- 在 B,我将 C 的成本设置为 3 + 7 = 10,将 A 的成本设置为 5。
- 现在 A 是成本最低的邻居,但访问它让我陷入困境,因为我无法出去。
如果我处理错误,我非常感谢您提出建议或更正。
最佳答案
由于 G 已被标记为已访问,因此不再考虑该节点,因此也考虑 A,因为没有更多可能的连接。
关于algorithm - 陷入Dijkstra算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53580570/