investigacion - dijkstra algorithm
¿Por qué el algoritmo de Dijkstra usa disminuir clave? (2)
En 2007, hubo un documento que estudió las diferencias en el tiempo de ejecución entre el uso de la versión de disminución de clave 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 utilizar 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 disminución de clave. Vea el documento para más detalles.
El algoritmo de Dijkstra que se me enseñó fue 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 muchas de las versiones que veo usan la tecla disminuir en lugar de insertar.
¿Por qué es esto y cuáles son las diferencias entre los dos enfoques?
La razón para usar la tecla disminuir en vez de reinsertar los nodos es mantener pequeña la cantidad de nodos en la cola de prioridad, disminuyendo así el número total de dequeues de cola de prioridad pequeña y el costo de cada cola de prioridad baja.
En una implementación del algoritmo de Dijkstra que reinserta los 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 del gráfico. Esto significa que hay operaciones de enqueue y m dequeue en la cola de prioridad, dando un tiempo de ejecución total de O (m T e + m T d ), donde T e es el tiempo requerido para enrutar a la cola de prioridad y T d es el tiempo requerido para quitar la cola de prioridad.
En una implementación del algoritmo de Dijkstra que admite la tecla disminuir, la cola de prioridad que contiene los nodos comienza con n nodos y en cada paso del algoritmo elimina un nodo. Esto significa que el número total de dequeues de montón es n. Cada nodo tendrá una tecla de disminución llamada en ella una vez por cada borde que lo conduzca, por lo que el número total de teclas de disminución hechas es como máximo m. Esto proporciona 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 disminuir.
Entonces, ¿qué efecto tiene esto en el tiempo de ejecución? Eso depende de la cola de prioridad que use. Aquí hay una tabla rápida que muestra diferentes colas de prioridad y los tiempos de ejecución generales de las diferentes implementaciones de 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 la versión de disminución de clave no es probable que lo haga mucho mejor. Sin embargo, si utiliza una implementación Fibonacci heap de la cola de prioridad, entonces, de hecho, el algoritmo de Dijkstra será más eficiente de manera asintótica cuando use la tecla disminuir.
En resumen, usar la tecla disminuir, más 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 sigues haciendo enqueues y dequeues.
Además de este punto, algunos algoritmos más avanzados, como el Algoritmo de trayectorias más cortas de Gabow, usan el algoritmo de Dijkstra como una subrutina y dependen en gran medida de la implementación de la tecla decreciente. Utilizan el hecho de que si conoce el rango de distancias válidas por adelantado, puede construir una cola de prioridad muy eficiente basada en ese hecho.
¡Espero que esto ayude!