Dijkstra处理一个负边，并给出正确的解决方案，一旦给出不正确的

Question

我知道这可能会被选为副本（因为我已经看到了这张使用Dijkstra算法的负权重图，所以我认为其中没有一个答案是我想要的。我对Dijkstra算法在有一条负边的图中的解感兴趣，但Dijkstra仍然会显示正确的解。那张图会是什么样子？我无法想象，或者我不擅长enough需要了解Dijkstra如何处理负边缘。我知道有一个带负边的图，可以用Dijkstra遍历，并且仍然有正确的路径。请不要告诉我使用贝尔曼·福特或约翰逊算法。

Answer 1

如果负边的绝对值小于无向图中任何其他边的权重，则Dijkstra算法可以很好地工作。

这确保了我们不会出现到从队列中弹出的节点的距离稍后会被更新的情况。与典型设置（仅为正权重）一样，一旦我们从队列中弹出一个节点，就可以保证我们无法通过较短的路径到达它。

注意：这不适用于有向图，在有向图中，从队列中弹出目标endpoint后可能会遇到负边的源endpoint（因此可能需要更新弹出的节点）。

Answer 2

例如，任何一个图，负边都会导致竖直，而竖直中没有边。

Answer 3

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