Algoritmo di Dijkstra
Il tuo navigatore conosce la via più rapida dalla tua porta a quasi ogni luogo. Al cuore di questa idea c'è un algoritmo che Edsger Dijkstra ideò in circa venti minuti nel 1956: espandersi dalla partenza e finire sempre prima il luogo più vicino.
L'idea
Immagina delle città collegate da strade di lunghezza diversa. La domanda è: qual è la via più breve dalla mia città a ciascuna delle altre? La visita in ampiezza risponde quando ogni strada conta allo stesso modo, ma qui un tragitto con più strade può essere più breve. L'algoritmo di Dijkstra tiene, per ogni città, la distanza più breve trovata finora e fa crescere una regione di città la cui distanza è certa, aggiungendo sempre la città più vicina che non è ancora certa.
Passo per passo
Dai alla partenza distanza 0 e a ogni altro nodo infinito. Metti la partenza in una coda di priorità, una coda che restituisce sempre il nodo con la distanza più piccola. Prendi quel nodo; la sua distanza ora è definitiva. Per ogni vicino non definitivo, calcola la distanza passando da questo nodo: la sua distanza più la lunghezza dell'arco. Se è minore della distanza attuale del vicino, abbassala, ricorda questo nodo come via per arrivarci e metti il vicino in coda. Questo si chiama rilassare un arco. Ripeti finché la coda è vuota, o finché l'arrivo esce dalla coda.
Un esempio
Prendi gli archi A–B di lunghezza 4, A–C 1, B–C 2, B–D 1, C–D 5 e D–E 3, e parti da A. Prendere A dà a B distanza 4 e a C distanza 1. C è il più vicino, quindi è definitivo a 1; passando da C, B scende a 1 + 2 = 3 e D riceve 1 + 5 = 6. Ora il più vicino è B, definitivo a 3, e passando da B, D scende a 3 + 1 = 4. D è definitivo a 4 e dà a E 4 + 3 = 7. Quindi la via più breve da A a E è A → C → B → D → E, lunga 7, anche se A → B → D → E usa meno archi ed è lunga 8.
Perché è corretto
Supponi che il nodo X sia il più vicino in coda, a distanza d. Ogni altro percorso dalla partenza a X deve uscire a un certo punto dalla regione dei nodi definitivi, e il primo nodo che raggiunge fuori da quella regione è in coda, quindi dista già almeno d. Il resto del percorso non può accorciarlo, perché nessun arco è negativo. Quindi d è la distanza più breve fino a X. Con un arco negativo questo ragionamento non regge; si usa invece l'algoritmo di Bellman–Ford, che rilassa tutti gli archi più e più volte.
Storia e usi
Edsger W. Dijkstra ideò l'algoritmo nel 1956 per mostrare un nuovo computer, l'ARMAC ad Amsterdam, trovando percorsi tra città olandesi, e lo pubblicò nel 1959. La stessa idea, con una coda più furba, funziona nei navigatori e nei protocolli di instradamento di Internet come OSPF e IS-IS, che calcolano la via più breve per i dati tra i router. L'algoritmo A* aggiunge una stima della distanza che resta da percorrere, così può puntare verso l'arrivo ed esaminare meno nodi.
Provalo
Apri l'app e premi Passo. I numeri sugli archi sono le loro lunghezze, e il numero su ogni nodo è la sua distanza finora. I nodi in coda sono blu, quelli definitivi verdi, e la coda sotto il grafo li elenca a partire dal più vicino, con le loro distanze. Osserva i momenti in cui una distanza scende perché un tragitto che sembrava più lungo si rivela più breve, e scegli un arrivo per vedere la ricerca fermarsi appena l'arrivo è definitivo.
Domande frequenti
Qual è la complessità temporale dell'algoritmo di Dijkstra?
Dipende dalla coda di priorità. Con una semplice lista è O(V²) per V nodi; con un heap binario O((V + E) log V) per E archi; con un heap di Fibonacci O(E + V log V), come mostrarono Michael Fredman e Robert Tarjan nel 1984.
L'algoritmo di Dijkstra funziona con pesi negativi sugli archi?
No. Presuppone che la distanza di un nodo non possa più migliorare una volta che il nodo è il più vicino in coda, e un arco negativo può smentirlo. Per grafi con archi negativi usa l'algoritmo di Bellman–Ford.
L'algoritmo di Dijkstra trova il percorso verso ogni nodo?
Sì. Eseguito fino in fondo, dà la distanza più breve dalla partenza a ogni nodo raggiungibile, e i nodi ricordati formano un albero dei percorsi più brevi. Fermarsi appena l'arrivo è definitivo fa risparmiare lavoro quando serve un solo percorso.
Che rapporto c'è tra l'algoritmo di Dijkstra e A*?
L'algoritmo A* è l'algoritmo di Dijkstra con un suggerimento: ordina la coda in base alla distanza finora più una stima della distanza che resta, come la distanza in linea d'aria su una mappa. Con una buona stima trova lo stesso percorso più breve esaminando molti meno nodi.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova l'algoritmo di Dijkstra