Perché l'algoritmo di Dijkstra usa il tasto di riduzione? Algoritmo

Question

di Dijkstra è stato insegnato a me era come segue

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) 

Ma ho fatto qualche lettura per quanto riguarda l'algoritmo, e un sacco di versioni vedo uso diminuzione-chiave al contrario di inserire.

Perché è questo, e quali sono le differenze tra i due approcci?

Answer 1

Il motivo per cui si utilizza il tasto di riduzione anziché reinserire i nodi è di mantenere piccolo il numero di nodi nella coda di priorità, riducendo quindi il numero totale di code di coda prioritarie ridotte e il costo di ciascun saldo di coda di priorità basso.

In un'implementazione dell'algoritmo di Dijkstra che reinserisce i nodi nella coda di priorità con le loro nuove priorità, un nodo viene aggiunto alla coda di priorità per ciascuno dei m bordi nel grafico. Ciò significa che ci sono operazioni m accodamento e operazioni m dequeue sulla coda di priorità, dando un'autonomia totale di O (m T _e + m T _d), dove T _e è il tempo richiesto per accodare nel priority queue e T _d è il tempo necessario per disconnettersi dalla coda di priorità.

In un'implementazione dell'algoritmo di Dijkstra che supporta il tasto di riduzione, la coda di priorità che contiene i nodi inizia con n nodi in esso e su ogni passo dell'algoritmo rimuove un nodo. Ciò significa che il numero totale di rotture di heap è n. Ogni nodo avrà un tasto di riduzione chiamato su di esso potenzialmente una volta per ogni spigolo che vi conduce, quindi il numero totale di chiavi decrepite è al massimo m. Questo dà un tempo di esecuzione (n T _e + n T _d + T _k m), dove T k è il tempo necessario per chiamare ridurre-chiave.

Quindi quale effetto ha questo runtime? Dipende dalla coda di priorità che usi. Ecco una tabella veloce che mette in mostra diverse code di priorità e tempi di esecuzione complessivi delle diverse implementazioni di 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) 

Come si può vedere, con la maggior parte dei tipi di code di priorità, non c'è davvero la differenza nel asintotico runtime, e la versione del tasto di diminuzione non dovrebbe fare molto meglio. Tuttavia, se si utilizza un'implementazione Fibonacci heap della coda di priorità, allora l'algoritmo di Dijkstra sarà asintoticamente più efficiente quando si utilizza il tasto di riduzione.

In breve, l'utilizzo del tasto di riduzione, oltre a una buona coda di priorità, può eliminare il tempo di esecuzione asintotico di Dijkstra oltre il possibile se continui a eseguire accodamenti e annullamenti.

Oltre a questo punto, alcuni algoritmi più avanzati, come l'algoritmo di Gabow Shortest Paths, utilizzano l'algoritmo di Dijkstra come subroutine e si basano molto sull'implementazione del tasto di riduzione. Usano il fatto che se si conosce l'intervallo di distanze valide in anticipo, è possibile creare una coda di priorità super efficiente basata su tale fatto.

Spero che questo aiuti!

Answer 2

Nel 2007, c'era un documento che studiava le differenze nei tempi di esecuzione tra l'uso della versione del tasto di riduzione e la versione di inserimento.Vedi http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

La loro conclusione di base era di non utilizzare il tasto di riduzione per la maggior parte dei grafici. Soprattutto per i grafici sparsi, la chiave non-diminuzione è significativamente più veloce rispetto alla versione con chiave decrescente. Vedi la carta per maggiori dettagli.