接受单个负边缘的 Dijsktra 算法

Question

所以我最近一直在研究 Dijkstra 的算法和有向图。但是，我似乎无法弄清楚这一点，这真的开始困扰我。

如果恰好有一个负权重边但没有负权重循环，则展示如何修改 Dijkstra 算法以解决单源最短路径问题。

到目前为止，我最初的想法是以某种方式拆分图形并分别执行算法，但这就是我想到的全部。

我实际上找到了我正在寻找的解释，但我似乎无法遵循他的解释

回答得好！我想指出的是，如果负边的数量有限，那么基于 Dijkstra 的算法可能会做得更好。例如，如果从u到v只有一个下降沿，你可以在S和V上运行Dijkstra算法，然后取最小值之间的每个顶点d[s]和d[s]+w(u, v)+d[v]，给人一种运行Dijkstra算法的复杂度的两倍

Answer 1

删除负边缘(u, v)，运行 Dijkstra 两次：一次从s( D1) 开始，一次从v( D2)开始

s和之间的最短路径t是：min(D1[t], D1[u]+D2[t]+w(u, v))。