algorithm - Dijkstra处理一个消极的边缘并给出正确的解决方案，而一旦给出不正确的

我知道这可能被选为重复（因为我已经看过这个Negative weights using Dijkstra's Algorithm我想没有任何答案，所以我正在寻找。
我对有一个负边的图的dijkstra算法的解感兴趣，但是dijkstra仍然会给出正确的解。那张图看起来怎么样？我无法想象，或者我还不足以理解dijkstra是如何处理负边的。我知道有一个负边的图，可以用dijkstra遍历，并且仍然有正确的路径。请不要告诉我使用贝尔曼福特或约翰逊的算法。

最佳答案

事实上，dijkstra的算法试图通过比较能够达到目标的路径成本，以最低的成本找到最短的路径。因此，它基本上节省了从起点到每个节点的最低成本，从而使您能够达到目标它通过将新成本与一个节点和最后一个节点进行比较来实现，因此如果负值不影响该顺序（负边是最短路径的一部分），则路径没有问题（但得到的路径成本是错误的）也有这样的情况，负边缘不能引导你达到目标（它不是任何路径的一部分），那么你在路径和成本上没有问题。也许你可以找到第三个例子，边缘是一条通向目标的路径的一部分，但它仍然不是最短路径的一部分。
希望这有帮助，
祝你好运。

关于algorithm - Dijkstra处理一个消极的边缘并给出正确的解决方案，而一旦给出不正确的，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36794667/