用堆优化后的地杰斯特拉算法 是否可以用来求 存在负权边的情况？

Question

其实具体我有两个问题。

1.我知道最原始的地杰斯特拉算法复杂度是O(n^2)，但是用堆优化后，我们不再用一个数组去标记一个节点的最短路径是否已经求出来，而是用队列是否为空作为结束循环的依据。所以堆优化后的地杰斯特拉是否能够用来求带有负权边的最短路径？

2.我觉得用堆之后的dij 其实 就跟spfa类似了，只是两个的思想不同，一个是优先队列，存放距离源点最近的点，而spfa只是一个简单的队列，缩小松弛的节点范围。不知道这样的理解是否正确？

希望大家帮我解决一下，想了很久，网上也没有具体的结论。

Answer 1

你好，Dijkstra算法，带有负权边的情况下无论用不用优先队列都是不可以的,你去画个例子就可以看出来了。而spfa却可以处理。你也说了Dijkstra算法和spfa的思想不一样，其实spfa，Dijkstra和BFS形式是有点类似。你不能说Dijkstra用了优先队列就和spfa类似了，不用优先队列就不类似了,因为用了优先队列所以形式上有点相似。优先队列只是优化了循环找最小值的方式。此外spfa算法时间效率不稳定，如果图十分复杂边很多，spfa时间效率就很低了。Dijkstra堆优化时间复杂度很稳定。