为什么Dijkstra算法必须在每一轮中提取min？

Question

考虑该图对于应用Dijkstra算法是有效的,即没有负边权重.我很难说服自己Dijkstra的算法只有在每轮选择最小距离节点被提取时才有效.什么构成提取除最小距离节点以外的任何东西的证据都会导致Dijkstra算法的失败？我正在寻找一个好的论点,但欢迎支持的例子.

Answer 1

如果提取非最小节点,那么您将提取一个节点,在提取时未知最短距离.它将在稍后计算,但不会再次提取节点,因此您将在最后留下至少一个错误的最小距离.

例:

你将拥有d[1] = 0,然后你将提取它,因为它是唯一提取的.

这将设置:

d[3] = 3
d[2] = 1

现在你应该提取2,但是让我们说你提取3.

你会设置d[4] = 4.

现在让我们说你提取2和设置d[3] = 2.

接下来,仅4提取.你提取它,你就完成了.

你留下了错误的价值d[4] = 4而不是d[4] = 3.

请注意,这假设您无法多次提取节点(在经典的Dijkstra算法中无法提取).如果你允许这样做,那么你的建议确实有用,但可能无论是效率还是Dijkstra都不再有效.