编辑元素时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);
}
我已经运行了几个文本案例,我知道每次通过并更新顶点的距离时,优先级队列没有正确地重新排序,但我不知道为什么。我在什么地方出错了吗
# 1 楼答案
您必须删除并重新插入编辑的每个元素。(实际元素,而不是虚拟元素!)。因此,每次更新
distances
,都需要删除并添加受更改的主菜影响的元素据我所知,这并不是Java独有的,但对于所有操作,每个以O(logn)运行的优先级队列都必须以这种方式工作
# 2 楼答案
问题是您更新了
distances
数组,但没有更新queue
中相应的条目。要更新队列中相应的对象,需要先删除,然后添加# 3 楼答案
Java的
PriorityQueue
的缺点是remove(Object)
需要O(n)时间,如果您想通过删除和再次添加元素来更新优先级,则需要O(n)时间。然而,它可以在时间O(log(n))内完成。由于我无法通过谷歌找到一个有效的实现,我尝试使用TreeSet
自己实现它(不过是在Kotlin中,因为我更喜欢那种语言而不是Java)。 这似乎有效,应该有O(log(n))用于添加/更新/删除(更新通过add
完成):# 4 楼答案
我通过将进程划分为时间段(时间调度器就可以了)并扩展本机优先级队列来解决这个问题。因此,我实现了一个notify方法,其中该方法的键是以下代码:
我希望有帮助
# 5 楼答案
您可以避免更新队列中的项目,只是在默认情况下将每个节点标记为visted=false,并在运行时向队列中添加新项目
然后从队列中弹出一个节点,仅当它以前没有被访问过时才对其进行处理
Dijkstra的算法保证每个节点只被访问一次,所以即使队列中有过时的节点,也永远不会真正处理它们
此外,如果将算法内部与图形数据结构分离,可能会更容易