Самый простой способ - использовать приоритетную очередь, а не заботиться о ранее добавленном ключе в приоритетной очереди.Это означает, что у вас будет каждый узел несколько раз в очереди, но это совсем не повредит алгоритму.Если вы посмотрите на него, все версии узла, которые были заменены, будут обнаружены позже, и к тому времени будет определено ближайшее расстояние.
Проверка if alt < dist[v]: из Википедии - это то, чтоделает эту работу.Время выполнения от этого только немного ухудшится, но если вам нужна очень быстрая версия, вам придется оптимизировать ее дальше.
ПРИМЕЧАНИЕ:
Как и любая оптимизация, этаследует обращаться с осторожностью и может привести к любопытным и трудным для поиска ошибкам (см., например, здесь ).В большинстве случаев достаточно просто использовать удаление и повторную вставку, но упомянутый трюк может немного ускорить ваш код, если ваша реализация Dijkstra является узким местом.
Самое главное: прежде чем пытаться это сделать,убедитесь, что ваша очередь приоритетов обрабатывает приоритет.Фактический приоритет в очереди никогда не должен изменяться, иначе вы можете испортить инварианты очереди, что означает, что элементы, хранящиеся в очереди, могут быть недоступны для поиска.Например, в Java приоритеты хранятся вместе с объектом, поэтому вам нужна дополнительная оболочка:
Это не будет работать:
import java.util.PriorityQueue;
// Store node information and priority together
class Node implements Comparable<Node> {
public int prio;
public Node(int prio) { this.prio = prio; }
public int compareTo(Node n) {
return Integer.compare(this.prio, n.prio);
}
}
...
...
PriorityQueue<Node> q = new PriorityQueue<Node>();
n = new Node(10);
q.add(n)
...
// let's update the priority
n.prio = 0;
// re-add
q.add(n);
// q may be broken now
Поскольку на n.prio=0 вы также меняетеприоритет объекта в очереди.Тем не менее, это будет работать нормально:
import java.util.PriorityQueue;
// Only node information
class Node {
// Whatever you need for your graph
public Node() {}
}
class PrioNode {
public Node n;
public int prio;
public PrioNode(Node n, int prio) {
this.n = n;
this.prio = prio;
}
public int compareTo(PrioNode p) {
return Integer.compare(this.prio, p.prio);
}
}
...
...
PriorityQueue<PrioNode> q = new PriorityQueue<PrioNode>();
n = new Node();
q.add(new PrioNode(n,10));
...
// let's update the priority and re-add
q.add(new PrioNode(n,0));
// Everything is fine, because we have not changed the value
// in the queue.