编辑元素时 Java 优先级队列重新排序

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

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

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

这是我运行算法的地方：

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

我已经运行了几个文本案例，并且我知道每次我检查并更新顶点距离时优先级队列都没有正确重新排序，但我不知道为什么。我在某个地方犯了错误吗？

正如您所发现的，每当添加或删除元素时，优先级队列不会重新排序所有元素。这样做会太昂贵（记住比较排序的 n log n 下限），而任何合理的优先级队列实现（包括PriorityQueue) 承诺在 O(log n) 内添加/删除节点。

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

PriorityQueue不提供 api 来通知它有关更改的节点，因为这需要它提供有效的节点查找，而其底层算法不支持。实现一个优先级队列是相当复杂的。这维基百科关于优先级队列的文章 http://en.wikipedia.org/wiki/Priority_queue#Effect_of_different_data_structures可能是阅读相关内容的一个很好的起点。不过，我不确定这样的实现会更快。

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

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 中元素的优先级，因此需要插入Steps 而不是Nodes.