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

Question

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

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

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

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 的最短路径！

现在我们知道了，如果用Simple BFS来求正整数的最短距离，会出现找不到最小路径的情况。那么，有人可以给我一个反例，我的错误实现将无法为图形打印正确的路径。请随意以我使用的图形格式（示例文本文件格式）给我答案。

到目前为止，我拥有的所有图表，两种实现都呈现了正确的结果。这不应该发生，因为糟糕的实现是运行时 (E+V)，我们知道如果没有至少 E log 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

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

在高层次上，您的算法通过找到一个“活动”节点（距离已降低的节点），然后扫描出边以激活所有需要更新其距离的相邻节点来工作。请注意，同一个节点可以被多次激活——事实上，一个节点可能会在每次其候选距离下降时被激活一次，这在算法的运行中可能会发生多次。此外，如果候选距离多次下降，您实现的算法可能会将同一个节点多次放入队列中，因此除了第一个之外的所有出队都可能是不必要的。总体而言，我预计这会导致大图的运行时受到很大影响。

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

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

Answer 2

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

例子：

考虑 3 个名为 AB C 的节点。

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

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

在Dijkstra的方法中，A->C根本不会被遍历，因为当使用最小堆时，A->B会先被遍历，B会被标记为“已遍历”，然后B->C会被遍历，并且，C将被标记为“已遍历”。现在，由于 C 已被标记为“已遍历”，因此永远不会检查路径 A->C（长度为 7）。

因此，正如您所看到的，在您的错误方法中，您将到达 C 2 次（A->C & A->B->C），而使用 Dijkstra 的方法，您只会到达 C 一次。

这个例子应该证明使用 Dijkstra 算法可以减少迭代次数。