Dijkstras算法似乎不起作用,我的理解必定是有缺陷的

Question

这是我对维基百科所描述的 Dijkstra算法如何处理下图的解释.

首先它标记到所有相邻节点的最短距离,因此A得到1而C得到7.然后它用当前最短路径选择邻居.这是A.原点被标记为已访问,不会再被考虑.从原点到B到A的最短(也是唯一)路径现在是12.A被标记为已访问.从原点到目的地到B的最短路径是13.B被标记为已访问.从Origin到C到目的地的最短路径是14,但这是前一个到C的最短路径的两倍,即7,所以14被丢弃.目的地现在标记为已访问.

目的地已被标记为已访问,因此算法已完成.这是结果:

所以我误解了描述？维基百科上的描述是错误的吗？或者我偶然发现了一个案例,显示Dijkstra的算法不正确(我非常怀疑)？我注意到选择的路径似乎是以贪婪的方式选择的,但显然这是算法的定义特征之一,但是在这种情况下它似乎给出了错误的结果.

Answer 1

为每个节点分配一个暂定距离值:为我们的初始节点设置为零,为所有其他节点设置为无穷大.标记未访问的所有节点.将初始节点设置为当前节点.创建一组称为未访问集的未访问节点,该节点由除初始节点之外的所有节点组成.(维基)

使用你的例子:

未访问

A = inf;
B = inf;
C = inf;
Dest = inf;

访问

Origin = 0;

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

O => A = 1;
O => C = 7;

我们现在在A.

从A,唯一的路径是B,这给了我们

O => AB = 12;
O => C = 7

C现在是最低距离,并且是新的当前节点

O => CD = 8

由于D是目的地且8 <12,因此选择路线CD.