当此常规队列版本也正确时，为什么Dijkstra的算法需要优先级队列? [英] Why does Dijkstra's algorithm need a priority queue when this regular queue version is also correct?

问题描述

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

I have read the following but please take a look at my code below.

为什么Dijkstra的算法使用堆(优先级队列)?

我有dijkstra的两个版本，一个带有PQueue的良好版本，一个带有常规链表队列的较差版本.

I have two versions of dijkstra, one good version with PQueue, and one bad version with regular linked list queue.

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);
                }
            }
        }
    }
}

我也可以使用如下文本文件创建图形

I also have graph creation with a text file like below

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

Both the implementation renders the following [0, 3, 2, 6] which is the shortest path indeed from 0 to 6!

现在我们知道，如果使用简单BFS查找具有正整数的最短距离，则在某些情况下，它将找不到最小路径.因此，有人可以给我提供一个反例，因为我的Bad实现无法为图形显示正确的路径.随意以我使用的图形格式(示例文本文件格式)给我答案.

Now we know, if a Simple BFS is used to find shortest distance with positive integers, there will be cases where it will not find the minimum path. So, can someone give me a counter example for which my Bad implementation will fail to print the right path for a graph. Feel free to give me the answer in the graph format (the sample text file format) that I used.

到目前为止，我拥有的所有图形都实现了正确的结果.这不应该发生，因为错误的实现是运行时(E + V)，而且我们知道，至少没有E log V才能找到最短路径.

So far all the graphs I have had, both implementations rendered the right result. This shouldn't happen because the bad implementation is runtime (E+V) and we know we can't find shortest path without at least 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的正确最短路径.

Both implementations renders [0, 3, 5, 6, 8, 10], which is the correct shortest path from 0-10.

推荐答案

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

I believe that the algorithm you've given is correct, but that it isn't as efficient as Dijkstra's algorithm.

在较高的层次上，您的算法的工作原理是找到一个活动的"节点(距离已降低的节点)，然后扫描输出边缘以激活所有需要更新其距离的相邻节点.注意，同一节点可以被激活多次-实际上，节点每次候选距离下降时都可能被激活一次，这在算法运行中可能多次发生.此外，如果候选距离多次下降，则您实施的算法可能会将同一节点多次放入队列中，因此有可能除第一个队列外的所有出队都是不必要的.总的来说，我希望这会给大型图形带来巨大的运行时冲击.

At a high level, your algorithm works by finding an "active" node (one whose distance has been lowered), then scanning the outgoing edges to activate all adjacent nodes that need their distance updated. Notice that the same node can be made active multiple times - in fact, it's possible that a node will be activated once per time its candidate distance drops, which can happen potentially many times in a run of the algorithm. Additionally, the algorithm you have implemented might put the same node into the queue multiple times if the candidate distance drops multiple times, so it's possible that all dequeues except the first will be unnecessary. Overall, I'd expect this would result in a pretty big runtime hit for large graphs.

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

In a sense, the algorithm you've implemented is a shortest paths algorithm, but it's not Dijkstra's algorithm. The main difference is that Dijkstra's algorithm uses a priority queue to ensure that every node is dequeued and processed once and exactly once, leading to much higher efficiency.

因此，我想我能给出的最佳答案是您的算法不是Dijkstra算法的实现，而Dijkstra算法使用优先级队列的原因是为了避免算法重复多次计算距离."

So I guess the best answer I can give is "your algorithm isn't an implementation of Dijkstra's algorithm, and the reason Dijkstra's algorithm uses a priority queue is to avoid recomputing distances multiple times in the way that your algorithm does."

这篇关于当此常规队列版本也正确时，为什么Dijkstra的算法需要优先级队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！