考虑该图对于应用 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 的。
关于algorithm - 为什么 Dijkstra 算法必须在每一轮中提取 min？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43238215/