问为什么迪克斯特拉的算法必须在每一轮中提取最小值？

EN

如果您提取一个非最小节点，那么您将提取一个在提取时不知道最短距离的节点。稍后将计算该节点，但不会再次提取该节点，因此在结束时至少会留下一个错误的最小距离。

示例：

​

​

您将有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的。