为什么 Dijkstra 算法必须在每一轮中提取 min？
Why is it mandatory that Dijkstra's algorithm extracts min in each round?
考虑该图对于应用 Dijkstra 算法是有效的，即没有负边权重。我很难说服自己 Dijkstra 的算法只有在选择提取每一轮中的最小距离节点时才有效。什么构成了提取除最小距离节点以外的任何内容都会导致 Dijkstra 算法失败的证据？
我正在寻找一个好的论据，但欢迎提供支持性的例子。
如果您提取一个非最小节点，那么您将提取一个在提取时不知道其最短距离的节点。后面会计算，但不会再提取节点，所以你最后至少会留下一个错误的最小距离。
示例：
您将有 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 的了。
考虑该图对于应用 Dijkstra 算法是有效的，即没有负边权重。我很难说服自己 Dijkstra 的算法只有在选择提取每一轮中的最小距离节点时才有效。什么构成了提取除最小距离节点以外的任何内容都会导致 Dijkstra 算法失败的证据？ 我正在寻找一个好的论据，但欢迎提供支持性的例子。
如果您提取一个非最小节点，那么您将提取一个在提取时不知道其最短距离的节点。后面会计算，但不会再提取节点，所以你最后至少会留下一个错误的最小距离。
示例：
您将有 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 的了。