为什么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的。