Почему уменьшение ключа в алгоритме Дейкстры занимает время O(logN)?

Question

Для обновления части,

for all neighbors w of u:
    if dist[w] > dist[u] + l(u,w)
        dist[w] = dist[u] + l(u,w)
        prev[w] = u
        decreasekey(H,w)

Здесь w - это идентификатор узла, я думаю, что это должна быть пара (ID, ключ), ключом которого является dist[ID]. Если это так, то поиск узла с идентификатором w в очереди с приоритетами должен стоить O(N) времени, а не O(logN). Тогда, почему клавиша снижения в алгоритме Дейкстры занимает время O(logN)?

Answer 1

Реализация кучи, используемая для Dijktra, отличается от обычной реализации очереди с приоритетами, поэтому встроенные библиотеки с приоритетами не помогут. Единственное решение - реализовать вашу кучу и отслеживать положение каждой вершины в куче в массиве. Вам нужно обновить указатели на вершины, когда вы вставляете или удаляете в кучу. Когда вам нужно выполнить уменьшение ключа в куче, у вас есть прямое расположение вершины в куче, и вы можете обновить значение ключа в этом месте. Используйте Heapify, чтобы изменить порядок кучи (которая занимает O(logn)).

Answer 2

Вы правы, говоря, что ключ уменьшения в очереди с приоритетом занимает O(N) время. Таким образом, чтобы заставить алгоритм работать в O(nlogn) время, у вас есть один из этих двух вариантов:

1. Реализуйте очередь с приоритетами, в которой вы будете хранить местоположение узла. Этот тип очереди приоритетов поддерживает удаление узла в O(log n) время. Вы можете найти реализацию (в Java) здесь. И код алгоритма Дейкстры, который использует этот IndexMinPriorityQueue здесь.

2. Вставьте новые значения в приоритетную очередь вместо операций lowerKey. Однако в худшем случае использование пространства увеличится до O(M) в то время как раньше это было O(N)где М - количество ребер. Вы можете проверить, что этот алгоритм также будет работать. Фактически это метод выбора в большинстве приложений, где число ребер в графе невелико и может уместиться в памяти.

   for(all neighbors w of u){
       if (dist[w] > dist[u] + l(u,w)) {
           dist[w] = dist[u] + l(u,w);
           prev[w] = u;
           insert(H,w);
       }
   }
   

Answer 3

В куче, lowerKey всегда принимает O(logN). доказательство