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

Question

我试图实现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);
    }

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

Answer 1

您必须删除并重新插入编辑的每个元素。（实际元素，而不是虚拟元素！）。因此，每次更新distances，都需要删除并添加受更改的主菜影响的元素

据我所知，这并不是Java独有的，但对于所有操作，每个以O（logn）运行的优先级队列都必须以这种方式工作

Answer 2

问题是您更新了distances数组，但没有更新queue中相应的条目。要更新队列中相应的对象，需要先删除，然后添加

Answer 3

Java的PriorityQueue的缺点是remove(Object)需要O（n）时间，如果您想通过删除和再次添加元素来更新优先级，则需要O（n）时间。然而，它可以在时间O（log（n））内完成。由于我无法通过谷歌找到一个有效的实现，我尝试使用TreeSet自己实现它（不过是在Kotlin中，因为我更喜欢那种语言而不是Java）。 这似乎有效，应该有O（log（n））用于添加/更新/删除（更新通过add完成）：

// update priority by adding element again (old occurrence is removed automatically)
class DynamicPriorityQueue<T>(isMaxQueue: Boolean = false) {

    private class MyComparator<A>(val queue: DynamicPriorityQueue<A>, isMaxQueue: Boolean) : Comparator<A> {
        val sign = if (isMaxQueue) -1 else 1

        override fun compare(o1: A, o2: A): Int {
            if (o1 == o2)
                return 0
            if (queue.priorities[o2]!! - queue.priorities[o1]!! < 0)
                return sign
            return -sign
        }

    }

    private val priorities = HashMap<T, Double>()
    private val treeSet = TreeSet<T>(MyComparator(this, isMaxQueue))

    val size: Int
        get() = treeSet.size

    fun isEmpty() = (size == 0)

    fun add(newElement: T, priority: Double) {
        if (newElement in priorities)
            treeSet.remove(newElement)
        priorities[newElement] = priority
        treeSet.add(newElement)
    }

    fun remove(element: T) {
        treeSet.remove(element)
        priorities.remove(element)
    }

    fun getPriorityOf(element: T): Double {
        return priorities[element]!!
    }


    fun first(): T = treeSet.first()
    fun poll(): T {
        val res = treeSet.pollFirst()
        priorities.remove(res)
        return res
    }

    fun pollWithPriority(): Pair<T, Double> {
        val res = treeSet.pollFirst()
        val priority = priorities[res]!!
        priorities.remove(res)
        return Pair(res, priority)
    }

}

Answer 4

我通过将进程划分为时间段（时间调度器就可以了）并扩展本机优先级队列来解决这个问题。因此，我实现了一个notify方法，其中该方法的键是以下代码：

// If queue has one or less elements, then it shouldn't need an ordering
// procedure
if (size() > 1)
{
    // holds the current size, as during this process the size will
    // be vary
    int tmpSize = size();
    for (int i = 1; i < tmpSize; i++)
    {
        add(poll());
    }
}

我希望有帮助

Answer 5

您可以避免更新队列中的项目，只是在默认情况下将每个节点标记为visted=false，并在运行时向队列中添加新项目

然后从队列中弹出一个节点，仅当它以前没有被访问过时才对其进行处理

Dijkstra的算法保证每个节点只被访问一次，所以即使队列中有过时的节点，也永远不会真正处理它们

此外，如果将算法内部与图形数据结构分离，可能会更容易

public void dijkstra(Node source) throws Exception{
    PriorityQueue q = new PriorityQueue();
    source.work.distance = 0;
    q.add(new DijkstraHeapItem(source));

    while(!q.isEmpty()){
        Node n = ((DijkstraHeapItem)q.remove()).node;
        Work w = n.work;

        if(!w.visited){
            w.visited = true;

            Iterator<Edge> adiacents = n.getEdgesIterator();
            while(adiacents.hasNext()){
                Edge e = adiacents.next();
                if(e.weight<0) throw new Exception("Negative weight!!");
                Integer relaxed = e.weight + w.distance;

                Node t = e.to;
                if (t.work.previous == null || t.work.distance > relaxed){
                    t.work.distance = relaxed;
                    t.work.previous = n;
                    q.add(new DijkstraHeapItem(t));
                }
            }
        }
    }
}