小编nov*_*ice的帖子

我正在尝试使用优先级队列来实现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; …