Я пытаюсь реализовать алгоритм 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);
}
Я запустил несколько текстовых случаев, и я знаю, что очередь приоритетов не изменяется правильно каждый раз, когда я просматриваю и обновляю расстояния для вершин, но я не знаю почему. Я сделал ошибку где-нибудь?