¿Por qué el algoritmo de Dijkstra utiliza una clave de disminución?

El algoritmo de Dijkstra que me enseñaron era el siguiente

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)

Pero he estado leyendo un poco sobre el algoritmo, y veo que muchas versiones usan la tecla de disminución en lugar de la inserción.

¿Por qué es esto y cuáles son las diferencias entre los dos enfoques?

La razón para usar la clave de reducción en lugar de reinsertar nodos es mantener pequeño el número de nodos en la cola de prioridad, manteniendo así el número total de eliminaciones de cola de prioridad pequeño y el costo de cada saldo de cola de prioridad bajo.

En una implementación del algoritmo de Dijkstra que reintroduce nodos en la cola de prioridad con sus nuevas prioridades, se agrega un nodo a la cola de prioridad para cada uno de los m bordes en el gráfico. Esto significa que hay operaciones en cola y operaciones en cola en la cola de prioridad, lo que da un tiempo de ejecución total de O (m T _e + m T _d ), donde T _e es el tiempo necesario para ingresar en la cola de prioridad y T _d es el tiempo necesario para salir de la cola de prioridad.

En una implementación del algoritmo de Dijkstra que admite la clave de disminución, la cola de prioridad que contiene los nodos comienza con n nodos y en cada paso del algoritmo se elimina un nodo. Esto significa que el número total de eliminaciones de cola del montón es n. Cada nodo tendrá una clave de disminución llamada potencialmente una vez por cada borde que lo ingrese, por lo que el número total de claves de disminución realizadas es como máximo m. Esto da un tiempo de ejecución de (n T _e + n T _d + m T _k ), donde T _k es el tiempo requerido para llamar a la tecla de disminución.

Entonces, ¿qué efecto tiene esto en el tiempo de ejecución? Eso depende de la cola de prioridad que utilice. Aquí hay una tabla rápida que muestra diferentes colas de prioridad y los tiempos de ejecución generales de las diferentes implementaciones del algoritmo de Dijkstra:

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)

Como puede ver, con la mayoría de los tipos de colas de prioridad, realmente no hay una diferencia en el tiempo de ejecución asintótico, y es probable que la versión de clave reducida no funcione mucho mejor. Sin embargo, si usa una implementación de montón de Fibonacci de la cola de prioridad, entonces, de hecho, el algoritmo de Dijkstra será asintóticamente más eficiente cuando use la tecla de disminución.

En resumen, usar la tecla de disminución, además de una buena cola de prioridad, puede reducir el tiempo de ejecución asintótico de Dijkstra más allá de lo que es posible si sigue haciendo cola y quita de cola.

Además de este punto, algunos algoritmos más avanzados, como el algoritmo de rutas más cortas de Gabow, utilizan el algoritmo de Dijkstra como una subrutina y dependen en gran medida de la implementación de la clave decreciente. Usan el hecho de que si conoce el rango de distancias válidas de antemano, puede construir una cola de prioridad súper eficiente basada en ese hecho.

¡Espero que esto ayude!

En 2007, hubo un artículo que estudió las diferencias en el tiempo de ejecución entre el uso de la versión de clave reducida y la versión de inserción. Ver http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Su conclusión básica fue no usar la tecla de disminución para la mayoría de los gráficos. Especialmente para gráficos dispersos, la clave de no disminución es significativamente más rápida que la versión de clave de disminución. Consulte el documento para obtener más detalles.

Hay dos formas de implementar Dijkstra: una usa un montón que admite la reducción de clave y otra un montón que no lo admite.

Ambos son válidos en general, pero generalmente se prefiere el último. A continuación, usaré 'm' para denotar el número de aristas y 'n' para denotar el número de vértices de nuestro gráfico:

Si desea la mejor complejidad posible en el peor de los casos, optaría por un montón de Fibonacci que admita la tecla de disminución: obtendrá una buena O (m + nlogn).

Si le importa el caso promedio, también podría usar un montón binario: obtendrá O (m + nlog (m / n) logn). La prueba está aquí , páginas 99/100. Si el gráfico es denso (m >> n), tanto este como el anterior tienden a O (m).

Si desea saber qué sucede si los ejecuta en gráficos reales, puede consultar este documento, como sugirió Mark Meketon en su respuesta.

Lo que mostrarán los resultados de los experimentos es que un montón "más simple" dará los mejores resultados en la mayoría de los casos.

De hecho, entre las implementaciones que usan una clave de disminución, Dijkstra funciona mejor cuando usa un montón binario simple o un montón de emparejamiento que cuando usa un montón de Fibonacci. Esto se debe a que los montones de Fibonacci involucran factores constantes más grandes y el número real de operaciones de disminución de clave tiende a ser mucho menor de lo que predice el peor de los casos.

Por razones similares, un montón que no tiene que admitir una operación de disminución de clave, tiene factores aún menos constantes y en realidad funciona mejor. Especialmente si el gráfico es escaso.