Algoritmo di Dijkstra con coda di priorità

L'algoritmo di Dijkstra trova il cammino minimo da un singolo nodo sorgente a tutti gli altri nodi di un grafo pesato con pesi degli archi non negativi. Funziona elaborando avidamente i nodi in ordine di distanza attualmente migliore: espande sempre il nodo non visitato più vicino. La struttura dati fondamentale è un min-heap (coda con priorità), che recupera in modo efficiente il nodo con la distanza più piccola.

Algoritmo di Dijkstra: (1) Inizializzi dist[source] = 0 e dist[all others] = inf. (2) Inserisca (0, source) in un min-heap. (3) Estragga il nodo u con la distanza più piccola. Se è già stato visitato con una distanza minore, lo ignori. (4) Per ogni vicino v di u: se dist[u] + weight(u,v) < dist[v], aggiorni dist[v] e inserisca (dist[v], v) nell'heap. (5) Ripeta finché l'heap non è vuoto.

Il modulo Python heapq implementa un min-heap. Rappresentiamo il grafo come una lista di adiacenza: graph[u] = [(v, weight), ...]. L'heap memorizza tuple (distance, node). Utilizziamo un set visited per ignorare le voci obsolete dell'heap, cioè quelle inserite prima che venisse trovato un cammino migliore.

Consideri un grafo con 5 nodi e gli archi: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). I cammini minimi dal nodo 0 sono: verso 1 passando per 0→2→1, con costo 3; verso 2, con costo 1; verso 3 passando per 0→2→1→3, con costo 4; verso 4 passando per 0→2→1→3→4, con costo 7. Dijkstra trova tutti questi cammini in un'unica esecuzione, non solo il cammino verso una singola destinazione.

La correttezza di Dijkstra si basa sul fatto che, una volta estratto un nodo dal min-heap, la sua distanza è definitiva. Questo vale solo se i pesi degli archi sono non negativi. Con un arco negativo u→v di peso -5, dopo aver visitato v potremmo trovare un cammino che passa per u e che è più breve, ma v è già contrassegnato come visitato. Un singolo arco negativo può invalidare tutti i calcoli delle distanze successivi.

Questo problema aggiunge un vincolo: al massimo k scali. Dijkstra standard non gestisce nativamente il conteggio dei passaggi. Soluzione: estendere lo stato a (cost, node, stops_remaining). Si può usare Dijkstra con questa 3-upla, oppure Bellman-Ford con k+1 passaggi di rilassamento. La versione modificata di Dijkstra si arresta quando stops_remaining raggiunge 0, impedendo ulteriori passaggi.

Con un heap binario, Dijkstra richiede O((V + E) log V) di tempo: ogni vertice viene estratto una volta (V estrazioni), ogni arco può causare un inserimento (E inserimenti) e ogni operazione sull'heap costa O(log V). Con un heap di Fibonacci, il limite migliora a O(E + V log V), ma heapq di Python è un heap binario. Per i grafi sparsi (E ≈ V), la versione con heap binario è O(V log V); per i grafi densi (E ≈ V²) è O(V² log V).

Per recuperare il cammino effettivo, non solo le distanze, si mantenga un array prev: quando si aggiorna dist[v], si imposti prev[v] = u. Al termine dell'algoritmo, si ricostruisca il cammino dalla sorgente alla destinazione procedendo a ritroso: si inizi da dst, si seguano i puntatori prev fino a source e si inverta il risultato.

Quando i nodi sono stringhe o interi non contigui, si usi un defaultdict(list) per la lista di adiacenza e un normale dict per le distanze. Questo è comune nei problemi di LeetCode, come Network Delay Time, in cui i nodi sono etichettati da 1 a n. Si ricordi di usare dist = {node: inf for node in all_nodes} e di controllare i nodi irraggiungibili dopo l'algoritmo.

Per i grafi non pesati, BFS trova i cammini minimi in O(V + E), più rapidamente rispetto a Dijkstra, che richiede O((V+E) log V). Dijkstra generalizza BFS ai grafi pesati usando una coda con priorità invece di una normale coda FIFO. Quando tutti i pesi degli archi sono uguali, Dijkstra si riduce a BFS. Si scelga BFS per i grafi non pesati, Dijkstra per i pesi non negativi e Bellman-Ford per i pesi negativi.

La versione di Dijkstra presentata nei manuali usa una coda con priorità dotata di decrease-key: quando la distanza di un nodo migliora, se ne aggiorna direttamente la priorità. Ciò richiede un heap di Fibonacci per ottenere O(E + V log V), ma è difficile da implementare. L'approccio della lazy deletion usato nei colloqui inserisce invece una nuova voce e ignora le estrazioni obsolete: è più semplice e comporta solo un sovraccarico di un fattore costante. In Python, la lazy deletion con heapq è l'implementazione standard nei colloqui tecnici.

Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.

In questa lezione ha imparato che: Dijkstra usa un min-heap per elaborare i nodi secondo l'ordine della migliore distanza corrente, richiede O((V+E) log V) di tempo e non funziona con gli archi dal peso negativo e le voci obsolete dell'heap vengono gestite controllando un insieme visited al momento dell'estrazione. Nel prossimo argomento tratteremo Bellman-Ford, che gestisce i pesi negativi tramite n-1 passaggi di rilassamento.