graph - Dijkstra 算法 : why do I end up stuck in this example?

Question

我一直在尝试跟踪以下无向图的 Dijkstra 最短路径算法:

(二)
/\
/\
6/\9
/\
/\
/\
(A)- 5 -(C)- 1 -(F)----2----(I)
\/
\/
4\/2
\/
\/
\/
(四)

为了澄清:
(N) 将代表节点，没有格式的数字将代表权重。
A 和 C 之间的边的权重为 5，
C 和 F 之间的边的权重为 1。


我将在这里概述我的过程:

由于 A 是我的初始节点，算法从这里开始。由于 D 是更便宜的路径，算法遍历到 D。A 现在被标记为已访问，这意味着我们不能再次遍历它。

在 D 处，很容易看出我们将移至 F。

F 是我开始遇到麻烦的地方。由于最短路径会将我带到 C，我被困在两个访问过的节点之间，无法到达 I。有人可以帮助我吗？

编辑:对不起图表人员，这个问题最初是通过电话提出的。我会尽快解决这个问题。

Answer 1

你处理它的方式是错误的。 “在 D 很容易看出我们将转向 F”，这是不正确的。您首先访问 D，然后访问 C，而不是 F。仔细查看算法及其作用。

一开始你访问 A，所以你有以下成本:6 到 B，5 到 C，4 到 D，其余节点的 INFINITE。

你首先去 D。你现在更新你的成本从 A 到 F(通过 D)到 6。你下一个要访问的节点不是 D，而是 C，因为它有 最低成本 (5) 所有未访问节点的 .从 A 到 F 通过 C 的成本是 6，这已经是您拥有的成本，因此无需更新。

从那里你有 B 和 F 之间的 6 平局。假设你先去 B，然后什么都没有发生，因为到 F 的最短路径已经是 6，而通过 B 去 F 需要 15，这更贵比你已经拥有的成本，所以不要更新成本。然后您访问 F，因为它在所有未访问节点中的成本最低。从那里你更新你到 I 的路径，它不再是 INFINITE 而是 8。

因此，从 A 到 I 的最短路径是以下序列: A - D - F - I 。