Algoritmo di Dijkstra
Trova il percorso più economico da una partenza a un arrivo. Prende sempre il punto più economico in attesa in una coda di priorità, così i costi si allargano dalla partenza come un’inondazione.
- tempo O((V + E) log V)
- spazio O(V)
- usa una coda di priorità
Cosa significano questi termini?
- Costo: quanto costa una mossa. Nel labirinto il terreno costa 1, il fango 3 e l’acqua 9; nel grafo è il numero sull’arco.
- Coda di priorità: una coda in cui passa prima il più economico, non il primo arrivato.
- Stima (h): un’ipotesi del costo che resta. A* resta esatto solo se non è mai troppo alta.
- Rilassare un arco: controllare se passare dal punto corrente dà a un vicino un costo più basso e, se sì, adottarlo.
- in coda
- attuale
- finito
- percorso più economico
- terreno · 1
- fango · 3
- acqua · 9
- muro
Nuovo: Partenza da A1 con costo 0. È l’unico elemento in coda.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli la palude. Il percorso più economico gira tutto intorno al fango: il doppio delle mosse della linea retta, eppure costa meno (34 contro 36).
Come funziona
Ogni punto riceve un costo: 0 la partenza, infinito il resto. Dijkstra tiene i punti raggiunti in una coda di priorità e prende sempre il più economico. Quel costo è allora definitivo, perché qualsiasi altro percorso dovrebbe passare per qualcosa di almeno altrettanto caro. Poi guarda ogni vicino: se passare dal punto appena preso costa meno del costo attuale del vicino, il vicino prende il nuovo costo e ricorda da dove arriva. Preso l’arrivo, quei collegamenti riportano indietro lungo il percorso più economico.
Quando conviene usarlo
Usa Dijkstra quando le mosse costano in modo diverso e nessuna costa meno di zero: mappe stradali e navigatori, instradamento di rete, la combinazione di voli più economica. Se ogni mossa costa uguale, BFS dà la stessa risposta in modo più semplice. Con costi negativi Dijkstra può sbagliare; per quelli c’è Bellman-Ford.