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

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

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)

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

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

Ответ 1

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

В реализации алгоритма Дейкстры, который повторно вставляет узлы в очередь приоритетов с их новыми приоритетами, один узел добавляется в очередь приоритетов для каждого из 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)

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

In fact, among the implementations that use a decrease-key, Dijkstra performs better when using a simple Binary heap or a Pairing heap than when it uses a Fibonacci heap. This is because Fibonacci heaps involve larger constant factors и the actual number of decrease-key operations tends to be much smaller than what the worst case predicts.

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