编辑元素时重新排序Java优先级队列 [英] Java Priority Queue reordering when editing elements

问题描述

我正在尝试使用优先级队列来实现Dijkstra算法以查找最短路径。在算法的每个步骤中，我删除距离优先级队列最短距离的顶点，然后更新优先级队列中每个邻居的距离。现在我读到Java中的优先级队列在编辑其中的元素（确定排序的元素）时不会重新排序，所以我试图通过插入和删除虚拟顶点来强制它重新排序。但这似乎并没有起作用，而且我一直试图解决这个问题。

I'm trying to implement Dijkstra's algorithm for finding shortest paths using a priority queue. In each step of the algorithm, I remove the vertex with the shortest distance from the priority queue, and then update the distances for each of its neighbors in the priority queue. Now I read that a Priority Queue in Java won't reorder when you edit the elements in it (the elements that determine the ordering), so I tried to force it to reorder by inserting and removing a dummy vertex. But this doesn't seem to be working, and I'm stuck trying to figure it out.

这是顶点对象和比较器的代码

This is the code for the vertex object and the comparator

class vertex {
    int v, d;
    public vertex(int num, int dis) {
        v=num;
        d=dis;
    }
}

class VertexComparator implements Comparator {
    public int compare (Object a, Object b) {
        vertex v1 = (vertex)a;
        vertex v2 = (vertex)b;
        return v1.d-v2.d;
    }
 }

这是我运行算法的地方：

Here is then where I run the algorithm:

    int[] distances=new int[p];
    Comparator<vertex> comparator = new VertexComparator();
    PriorityQueue<vertex> queue = new PriorityQueue<vertex>(p, comparator);
    for(int i=0; i<p; i++) {
        if(i!=v) {
            distances[i]=MAX;
        }
        else {
            distances[i]=0;
        }
        queue.add(new vertex(i, distances[i]));
    }
    // run dijkstra
    for(int i=0; i<p; i++) {
        vertex cur=queue.poll();
        Iterator itr = queue.iterator();
        while(itr.hasNext()) {
            vertex test = (vertex)(itr.next());
            if(graph[cur.v][test.v]!=-1) {
                test.d=Math.min(test.d, cur.d+graph[cur.v][test.v]);
                distances[test.v]=test.d;
            }
        }
        // force the PQ to resort by adding and then removing a dummy vertex
        vertex resort = new vertex(-1, -1);
        queue.add(resort);
        queue.remove(resort);
    }

我运行了几个文本案例，我知道优先级队列不是每次我通过并更新顶点的距离时都要正确重新排序，但我不知道为什么。我是否在某处犯了错误？

I've run several text cases, and I know that the priority queue isn't reordering correctly each time I go through and update the distances for vertices, but I don't know why. Did I make an error somewhere?

推荐答案

正如您所发现的，只要添加了元素，优先级队列就不会求助所有元素或除去。这样做太昂贵了（记住n log n下限用于比较排序），而任何合理的优先级队列实现（包括 PriorityQueue ）都承诺在O中添加/删除节点（记录n）。

As you discovered, a priority queue does not resort all elements whenever an element is added or removed. Doing that would be too expensive (remember the n log n lower bound for comparison sort), while any reasonable priority queue implementation (including PriorityQueue) promises to add/remove nodes in O(log n).

实际上，它根本不对其元素进行排序（这就是为什么它的迭代器不能保证按排序顺序迭代元素）。

In fact, it doesn't sort its elements at all (that's why its iterator can not promise to iterate elements in sorted order).

PriorityQueue 不提供api来通知它有关已更改的节点，因为这需要它提供有效的节点查找，其基础算法不支持。实现一个非常复杂的优先级队列。 有关PriorityQueues的维基百科文章可能是阅读相关内容的良好起点。我不确定这样的实现会更快。

PriorityQueue does not offer an api to inform it about a changed node, as that would require it to provide efficient node lookup, which its underlying algorithm does not support. Implementing a priority queue that does is quite involved. The Wikipedia article on PriorityQueues might be a good starting point for reading about that. I am not certain such an implementation would be faster, though.

一个简单的想法是删除然后添加更改的节点。 不这样做 remove（）需要O（n）。相反，将相同节点的另一个条目插入PriorityQueue，并在轮询队列时忽略重复项，即执行以下操作：

A straightforward idea is to remove and then add the changed node. Do not do that as remove() takes O(n). Instead, insert another entry for the same node into the PriorityQueue, and ignore duplicates when polling the queue, i.e. do something like:

PriorityQueue<Step> queue = new PriorityQueue();

void findShortestPath(Node start) {
    start.distance = 0;
    queue.addAll(start.steps());

    Step step;
    while ((step = queue.poll()) != null) {
        Node node = step.target;
        if (!node.reached) {
            node.reached = true;
            node.distance = step.distance;
            queue.addAll(node.steps());
        }
    }

}

编辑：不建议更改PQ中元素的优先级，因此需要插入步骤而不是节点 s。

It is not advisable to change the priorities of elements in the PQ, hence the need to insert Steps instead of Nodes.

这篇关于编辑元素时重新排序Java优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！