为什么Dijkstra的算法需要一个优先级队列，而这个常规队列版本也是正确的？

Question

我已经阅读了以下内容，但请看看下面的代码。

为什么Dijkstra的算法使用堆（优先级队列）？

我有两个版本的dijkstra，一个是带有PQUE的好版本，另一个是带有常规链表队列的坏版本。

public static void computeDijkstra(Vertex source) {
    source.minDistance = 0.;
    Queue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    // Queue<Vertex> vertexQueue = new LinkedList<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex fromVertex = vertexQueue.poll();

        if (fromVertex.neighbors != null) {
            for (Edge currentEdge : fromVertex.neighbors) {
                Vertex toVertex = currentEdge.target;
                if (currentEdge.weight + fromVertex.minDistance < toVertex.minDistance) {
                    toVertex.minDistance = currentEdge.weight + fromVertex.minDistance;
                    toVertex.previous = fromVertex;
                    vertexQueue.add(toVertex);
                }
            }
        }
    }
}

public static void computeDijkstraBad(Vertex source) {
    source.minDistance = 0.;
    // Queue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    Queue<Vertex> vertexQueue = new LinkedList<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex fromVertex = vertexQueue.poll();

        if (fromVertex.neighbors != null) {
            for (Edge currentEdge : fromVertex.neighbors) {
                Vertex toVertex = currentEdge.target;
                if (currentEdge.weight + fromVertex.minDistance < toVertex.minDistance) {
                    toVertex.minDistance = currentEdge.weight + fromVertex.minDistance;
                    toVertex.previous = fromVertex;
                    vertexQueue.add(toVertex);
                }
            }
        }
    }
}

我也有图形创建的文本文件如下

0, 1, 2, 3, 4, 5, 6 // vertices
0, 6 // from and to vertex
1, (2-5, 0-4, 4-6) // from vertex 1 it will have edge to 2 with weight 5 ...
0, (4-3, 3-7)
4, (2-11, 3-8)
3, (2-2, 5-5)
2, (6-2, 5-10)
5, (6-3)

两个实现都呈现以下[0,3,2,6]，这是从0到6的最短路径！

现在我们知道了，如果用一个简单的BFS来寻找具有正整数的最短距离，那么在某些情况下它将无法找到最小路径。那么，有人能给我一个反例吗？我糟糕的实现将无法打印出正确的图形路径。请随意以我使用的图形格式（示例文本文件格式）给我答案。

到目前为止，我所拥有的所有图形，两个实现都呈现了正确的结果。这不应该发生，因为坏的实现是运行时（EV），我们知道如果没有至少Elog V，我们就找不到最短路径。

另一个例子，

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
0, 10
0, (1-9, 2-10, 3-11)
1, (4-1, 5-7)
2, (4-4, 5-3, 6-5)
3, (5-1, 6-4)
4, (7-9, 8-14, 5-3)
5, (7-4, 8-5, 9-9, 6-2)
6, (8-2, 9-2)
7, (10-3)
8, (10-2)
9, (10-5)

两种实现都呈现[0,3,5,6,8,10]，这是从0到10的正确最短路径。

Answer 1

阅读别人的答案，他们是对的，总结是坏的实现方法是正确的，但是所有者的索赔（O（E V））的复杂性不是对的。还有一件事是其他人没有提到的，我将在这里补充它。

这种糟糕的实现还对应于一种算法，它实际上是BFS的衍生物，正式称为SPFA。查看SPFA算法。当作者在1994年发表这个算法时，他声称它在O（E）复杂度方面比Dijkstra有更好的性能，这是错误的。

它在ACM学生中非常流行。由于它的简单性和易于实现。至于表现，迪克斯特拉是首选。

类似的回复参考了这篇文章

Answer 2

你的算法会找到正确的结果，但是你的方法正在做的是它扼杀了Dijkstra方法的效率。

例子：

考虑3个名为A B C的节点。

A->C :7 
A->B :2
B->C :3

在糟糕的方法中，首先将从A到C的最短路径设置为7，然后在遍历时将其修改为5（A）-

在Dijkstra的方法中-

因此，正如你所看到的，在你糟糕的方法中，你将达到C2倍（A-

这个例子应该证明，使用Dijkstra算法的迭代次数更少。

Answer 3

我相信你给出的算法是正确的，但是它不如Dijkstra的算法有效。

在较高级别上，您的算法通过查找一个“活动”节点（距离已降低的节点）来工作，然后扫描输出边以激活所有需要更新其距离的相邻节点。请注意，同一节点可以被激活多次——事实上，一个节点有可能在其候选距离下降时被激活一次，这可能在算法运行中发生多次。此外，如果候选距离多次下降，您所实现的算法可能会多次将同一节点放入队列，因此，除第一个节点外，所有的出列都可能是不必要的。总的来说，我认为这将导致大型图在运行时受到相当大的冲击。

从某种意义上说，您实现的算法是最短路径算法，但它不是Dijkstra算法。主要区别在于Dijkstra的算法使用优先级队列来确保每个节点一次且准确地退出队列并处理一次，从而提高了效率。

所以我想我能给出的最好答案是“你的算法不是Dijkstra算法的实现，Dijkstra算法使用优先级队列的原因是为了避免像你的算法那样多次重新计算距离。”