我对此有一个后续问题： 在最多包含两个负边的图中找到最短路径距离
Ranveer 的解决方案看起来不错，但速度不够快，因为我需要 O(|E| + |V|*log|V|) 快速算法。
我猜杜克林的解决方案效果很好。这是有道理的，它的运行时间与 Dijkstra 算法的运行时间相同。
但是，我的目标是找到从给定节点 s 到 V 中所有节点的最短路径距离。如果我通过将 V 中的所有节点设置为结束顶点 e 来应用 Dukeling 算法，我将需要运行它 |V| - 1 次。那么，运行时间将是 O(|V||E| + |V^2|*log|V|)。
任何帮助，将不胜感激！
Dijkstra 算法以其原始形式查找从源节点到图中所有其他节点的所有最短路径。
对于您的问题，您有（至少）两个选项：
使用贝尔曼-福特。它并不像它的大哦所暗示的那么慢，至少不一定。确保您像执行BF 搜索一样实现它：使用FIFO 队列。这意味着每次更新到它的距离时，您都会将一个节点插入队列中，并且仅当它尚未在队列中时。其他优化也是可能的，但这应该已经在实践中为您提供了一个快速算法；
使用Dijkstra's，但修改与 Bellman - Ford 类似：默认 Dijkstra's 从不将节点两次插入优先级队列。如果您已更新到节点的距离，请确保重新插入节点。这将处理负成本边缘。它本质上使算法更接近上述贝尔曼 - 福特，但使用优先级队列而不是 FIFO 队列。这也将使您更接近所需的复杂性。