algorithm - 负权重的 Dijkstra 算法

Question

现在我知道如果图形包含负权重边，Dijkstra 将无法工作。但是有一个异常(exception)。 (只有离开源的边可以具有负权重，而所有其他边必须为正。)

我想证明这一点。我不知道如何开始。我制作了一些图表，在所有这些图表中，Dijkstra 最终都能完美地工作，但我不明白如何证明这一点？

所以我真正想要的是有人证明 Dijkstra 在这种情况下会起作用或不会(只有来自源的出边是负数。)

此外，图表不能包含任何涉及源的循环。

Answer 1

首先要注意的是，如果没有涉及源的循环，我们可以对任何进入源的边进行裁剪，这不会影响结果，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 是来源)，不等式仍然存在。