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

Алгоритм Дейкстры был представлен мне следующим образом

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

Но я немного читал об алгоритме, и многие версии, которые я вижу, используют клавишу уменьшения, а не вставку.

Почему это так и в чем разница между этими двумя подходами?

Причина использования ключа уменьшения вместо повторной вставки узлов состоит в том, чтобы сохранить небольшое количество узлов в очереди с приоритетами, таким образом, сохраняя небольшое общее количество исключений очереди с приоритетами и низкую стоимость каждого баланса очереди с приоритетами.

В реализации алгоритма Дейкстры, который повторно вставляет узлы в приоритетную очередь с их новыми приоритетами, один узел добавляется в приоритетную очередь для каждого из m ребер в графе. Это означает, что в приоритетной очереди есть m операций постановки в очередь и m операций постановки из очереди, что дает общее время выполнения O (m T _e + m T _d ), где T _e - время, необходимое для постановки в очередь с приоритетом, а T _d - время, необходимое для выхода из очереди с приоритетом.

В реализации алгоритма Дейкстры, который поддерживает уменьшение ключа, приоритетная очередь, содержащая узлы, начинается с n узлов в ней и на каждом шаге алгоритма удаляет один узел. Это означает, что общее количество исключений из кучи равно n. Каждый узел будет иметь кнопку уменьшения, вызываемую потенциально один раз для каждого ребра, ведущего в него, поэтому общее количество выполненных ключей уменьшения не превышает m. Это дает время выполнения (n T _e + n T _d + m T _k ), где T _k - время, необходимое для вызова клавиши уменьшения.

Итак, как это влияет на время выполнения? Это зависит от того, какую приоритетную очередь вы используете. Вот краткая таблица, в которой показаны разные очереди приоритетов и общее время выполнения различных реализаций алгоритма Дейкстры:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

Как видите, с большинством типов очередей приоритетов действительно нет разницы в асимптотической среде выполнения, и версия с уменьшающимся ключом вряд ли будет намного лучше. Однако, если вы используете реализацию очереди приоритетов кучи Фибоначчи , тогда действительно алгоритм Дейкстры будет асимптотически более эффективным при использовании ключа уменьшения.

Короче говоря, использование клавиши уменьшения плюс хорошая очередь с приоритетом могут снизить асимптотическое время выполнения Дейкстры за пределы возможного, если вы продолжаете ставить в очередь и удалять из очереди.

Помимо этого, некоторые более продвинутые алгоритмы, такие как алгоритм кратчайшего пути Габоу, используют алгоритм Дейкстры в качестве подпрограммы и в значительной степени полагаются на реализацию с уменьшением ключа. Они используют тот факт, что если вы заранее знаете диапазон допустимых расстояний, вы можете построить суперэффективную очередь с приоритетом на основе этого факта.

Надеюсь это поможет!

В 2007 году была опубликована статья, в которой изучалась разница во времени выполнения между версией с уменьшенным ключом и версией со вставкой. См. Http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf.

Их основной вывод заключался в том, что не следует использовать кнопку уменьшения для большинства графиков. Ключ без уменьшения, особенно для разреженных графиков, работает значительно быстрее, чем версия с ключом уменьшения. См. Статью для более подробной информации.

Есть два способа реализовать Dijkstra: один использует кучу, которая поддерживает клавишу уменьшения, а другой - кучу, которая этого не поддерживает.

Оба они действительны в целом, но обычно предпочтительнее последнее. Далее я буду использовать букву m для обозначения количества ребер и n для обозначения количества вершин нашего графа:

Если вам нужна наилучшая возможная сложность наихудшего случая, вы должны пойти с кучей Фибоначчи, которая поддерживает клавишу уменьшения: вы получите хороший O (m + nlogn).

Если вас интересует средний случай, вы также можете использовать двоичную кучу: вы получите O (m + nlog (m / n) logn). Доказательство здесь , страницы 99/100. Если граф плотный (m >> n), и этот, и предыдущий стремятся к O (m).

Если вы хотите узнать, что произойдет, если вы запустите их на реальных графиках, вы можете проверить эту статью, как предложил Марк Мекетон в своем ответе.

Результаты экспериментов покажут, что "более простая" куча в большинстве случаев дает наилучшие результаты.

Фактически, среди реализаций, в которых используется клавиша уменьшения, Dijkstra лучше работает при использовании простой двоичной кучи или кучи Pairing, чем при использовании кучи Фибоначчи. Это связано с тем, что куча Фибоначчи включает в себя более крупные постоянные коэффициенты, а фактическое количество операций с уменьшением ключа имеет тенденцию быть намного меньше, чем прогнозируется в худшем случае.

По тем же причинам куча, которая не должна поддерживать операцию уменьшения ключа, имеет еще меньше постоянных факторов и фактически работает лучше всего. Особенно, если график разреженный.