Algoritmo di Dijkstra con coda di priorità

Question

Nella mia implementazione dell'algoritmo di Dijkstra ho 1 array con tutti i nodi e 1 coda di priorità con tutti i nodi. Ogni volta che un nodo viene rimosso dalla coda, aggiorno tutti i nodi adiacenti con una nuova distanza e da dove proviene, quindi posso tornare indietro del percorso.

Il nodo nella coda di priorità viene aggiornato con una nuova distanza e il nodo nell'array viene aggiornato da dove proviene e con nuova distanza. Quando un nodo viene rimossa dalla coda la distanza finale nella matrice viene aggiornata:

PathInfo current = pq.remove(); 
    path[current.pos].distance = current.distance; 

È accettabile aggiornare sia l'array con informazioni inerenti precedente nodo e la coda di priorità con la distanza?

Questo avviene ogni volta che viene trovata una distanza meglio:

 PathInfo key(i, newDistance); 
     path[i].distance = newDistance; 
     path[i].previous = current.pos; 
     pq.decreaseKey(key); 

Sembra un po 'ridondante per modificare il mio allineamento e coda di priorità con sostanzialmente le stesse informazioni.

Attualmente sto utilizzando un array normale come struttura dati nel PQ. L'aggiornamento della priorità viene eseguito in tempo lineare e la dequeue viene eseguita anche in tempo lineare.

Quale struttura dati dovrei usare nella coda di priorità e come dovrei cambiare la priorità di un nodo?

sto usando C++

Answer 1

Qui ci sono due tipi di distanze: la coda di priorità ha "distanze provvisorie" che sono soggetti ad aggiornamento, mentre l'array ha "distanze finali", che non lo sono (perché l'algoritmo di Dijkstra non ha bisogno di aggiornare i nodi che sono stati rimossi dalla coda di priorità).

Sembra che si aggiorni inutilmente le distanze nell'array. Forse sarebbe anche una buona idea cambiare il nome del campo nel tuo nodo array per documentarlo: da arrayNode.distance a arrayNode.finalDistance.

In altre parole: sembra che si stiano utilizzando i nodi della matrice per produrre i risultati dall'algoritmo di Dijkstra, quindi è necessario impostare la distanza in ciascun nodo della matrice solo una volta, quando viene rimossa dalla coda di priorità.

---

Se l'implementazione coda con priorità non fornisce la possibilità di interrogare la distanza corrente associato con una data chiave, si prega di verificare il comportamento del suo funzionamento decreaseKey(). Se l'operazione decreaseKey() rifiuta gli aggiornamenti per i quali la nuova priorità non diminuisce, non è necessario eseguirla da soli: è sufficiente chiamarla per ciascun vicino del nodo corrente.

Tuttavia, se la funzione decreaseKey() non gestisce questo caso correttamente, e non v'è alcuna funzione di query ausiliaria che consentono di eseguire tale controllo manualmente, e non v'è alcuna possibilità di risolvere entrambi i deficit, allora avrete bisogno di mantenere informazioni ridondanti a tale scopo ....

Answer 2

Strutture dati che si possono utilizzare:

• Min Heap
• Segment Tree
• Fenwick tree

Forse qualche altro per trovare il minimo in array.

Quando si aggiorna la priorità sul nodo, è necessario sincronizzare la struttura dati che si preferisce.

Nota: Se è stato utilizzato matrice per controllare nodo collegato, si può semplicemente non utilizzare la struttura dati non cambia algo complessità sarò ancora O (N^2) (utilizzare ciclo diretto per trovare nodo con adeguata priorità) Struttura dati efficace quando il grafico ha molti nodi e piccole quantità di connessioni e memorizzato come elenco di nodi connessi (grafici scaricati)