¿Por qué el algoritmo de Dijkstra usa la tecla disminuir? algoritmo de Dijkstra

Question

se le enseñó a mí era la siguiente manera

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 haciendo un poco de lectura en relación con el algoritmo, y una gran cantidad de versiones que ver el uso disminución de clave en contraposición a insertar.

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

Answer 1

La razón para usar la tecla disminuir en lugar de reinsertar los nodos es mantener pequeña la cantidad de nodos en la cola de prioridad, disminuyendo el número total de colas de cola de prioridad pequeñas y el costo de cada cola de prioridad baja.

En una implementación del algoritmo de Dijkstra que reinserta 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 no son operaciones m enqueue y operaciones 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 necesario para poner en cola en el cola de prioridad y T _d es el tiempo requerido para quitar la cola de 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 da un tiempo de ejecución de (n T _e + n T _d + T _k m), donde T _k es el tiempo requerido para llamar a disminuir de clave.

¿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 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 se puede ver, la mayoría de los tipos de colas de prioridad, en realidad no hay una diferencia en el asintótica tiempo de ejecución, y la versión de disminución de clave no es probable que lo haga mucho mejor. Sin embargo, si utiliza una implementación de Fibonacci heap de la cola de prioridad, entonces, de hecho, el algoritmo de Dijkstra será más eficiente de manera asintótica al usar la tecla de disminución.

En resumen, usar la tecla de reducción, más una buena cola de prioridad, puede hacer descender el tiempo de ejecución asintótico de Dijkstra más allá de lo que es posible si continúa 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!

Answer 2

En 2007, hubo un documento que estudió las diferencias en el tiempo de ejecución entre el uso de la versión de la tecla de disminución 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.