algorithm - 接受单个负边的 Dijkstra 算法

Question

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

Show how to modify Dijkstra’s algorithm to solve the single source shortest path problem if there is exactly one negative weight edge but no negative weight cycles.

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

我实际上已经找到了我正在寻找的解释，但我似乎无法理解 his explanation

Well answered! I'd like to point out that if the number of negative edges is limited, there are Dijkstra-based algorithms that might do a better job. For example, if there is only one negative edge from u to v, you could run Dijkstra on s and on v, and then take the minimum for each vertex between d[s] and d[s]+w(u, v)+d[v], giving a complexity of running Dijkstra twice

Answer 1

去除负边(u, v) ，运行 Dijkstra 两次:一次从 s 开始( D1 ) 一旦从 v 开始( D2 )

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