algorithm - Dijkstra 处理一个下降沿并给出正确的解决方案，一旦给出不正确的解决方案

Question

我知道这可能会被选为重复项(因为我已经看过这个 Negative weights using Dijkstra's Algorithm 我认为 SO 中没有一个答案是我要找的。我对 Graph 中具有一个负边的 Dijkstra 算法的解决方案感兴趣，但 Dijkstra 仍将显示正确的解决方案。该图会是什么样子？我无法想象，或者我还不够好，根本无法理解 Dijkstra 是如何处理负面边缘的。而且我知道有一个带有负边的图可以用 Dijkstra 遍历并且仍然有正确的路径。请不要告诉我使用 Bellman-Ford 或 Johnson 的算法。

Answer 1

事实上，Dijkstra 算法试图通过比较可以达到目标的路径成本来找到最短路径，并选择成本最低的路径。因此，它基本上可以节省从起点到可以使您到达目标的每个节点的最低成本。它通过将新成本与节点和最后一个节点进行比较来做到这一点，因此如果负值不影响该顺序(负边缘是最短路径的一部分)则路径没有问题(但你得到错误路径成本)。还有一种情况是负边不能把你带到目标(它不是任何路径的一部分)，那么你在路径和成本上都没有问题。也许你可以找到第三个例子，边缘是将你带到目标的路径之一的一部分，但它仍然不是最短路径的一部分。希望这有帮助，祝你好运。