问Dijsktra接受单一负边的算法

EN

所以我最近一直在研究Dijkstra的算法和有向图。然而，我似乎不明白这一点，这真的开始困扰我。

说明了如何修改Dijkstra的算法，以解决单源最短路径问题，如果正好有一个负权边，但没有负权循环。

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

我确实找到了一个我想要的解释，但我似乎跟不上his explanation

回答得好！我想指出的是，如果负边的数目是有限的，那么基于Dijkstra的算法可能会做得更好。例如，如果从u到v只有一个负边，您可以在s上和v上运行Dijkstra，然后取d[s]和d[s]+w(u, v)+d[v]之间的每个顶点的最小值，从而使运行Dijkstra的复杂性达到两次。