现在我知道如果图表包含负权重边，Dijkstra 将不起作用。但有一个异常(exception)。 (只有离开源的边可以具有负权重，而所有其他边必须为正。)
我希望能够证明这一点。我不知道如何开始。我制作了一些图表，在所有这些图表中，Dijkstra 最终都完美地工作，但我不明白如何证明这一点？
所以我真正想要的是有人证明 Dijkstra 在这种情况下会起作用或不会(只有来自源的传出边是负的。)
此外，图表不能包含任何涉及源的循环。
最佳答案
首先注意，如果没有涉及源的循环，我们可以对传入源的任何边修剪图，并且不会影响结果，在 Dijkstra 算法中不会到达通向源的顶点无论如何(否则，就会存在涉及源的循环)。
从现在开始，我们假设源没有传入边缘。
请注意，松弛步骤所需的声明(三角不等式):d(u,v) <= d(u,x) + w(x,v)必须(空)保存每个w(x,v) < 0 ，唯一u其中存在一条来自 u 的路径至x (这是来源)是 u=x=source ，路径为空路径。
这将我们引向d(u,x) + w(x,v) = 0 + w(x,v) = w(u,v) = d(u,v) (其中 u 是源)，并且不等式仍然成立。
关于algorithm - 负权重的 Dijkstra 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30026724/