Algoritmo di Dijkstra
- Introdotto da
- Edsger W. Dijkstra
- Anno
- 1956
- Tipo
- algorithm
- Famiglia
- Graph Algorithms
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'Algoritmo di Dijkstra, introdotto da Edsger W. Dijkstra nel 1956, è uno degli algoritmi più fondamentali dell'informatica per risolvere il problema del cammino minimo da sorgente singola.
Trova il cammino più breve da un vertice di partenza a tutti gli altri vertici in un grafo pesato con pesi degli archi non negativi.
L’intuizione alla base del metodo
L'algoritmo mantiene un insieme di vertici le cui distanze minime dalla sorgente sono già note, ed espande iterativamente questo insieme selezionando il vertice non processato più vicino e aggiornando le distanze dei suoi vicini. L'intuizione chiave è la proprietà greedy: una volta selezionato un vertice, la sua distanza dalla sorgente è definitiva perché tutti i pesi degli archi sono non negativi, quindi qualsiasi cammino più lungo attraverso vertici non visitati non può essere più breve. Questo garantisce correttezza e ottimalità.
Storia
Edsger W. Dijkstra pubblicò il suo algoritmo nel 1959 in un articolo di tre pagine che sarebbe diventato uno dei lavori più citati dell'informatica. L'algoritmo emerse dal lavoro di Dijkstra sul computer ARMAC ad Amsterdam. Nel corso dei decenni, sono stati apportati numerosi miglioramenti, tra cui migliori strutture dati (heap di Fibonacci che raggiungono una complessità O(E+VlogV)) e varianti bidirezionali. L'algoritmo rimane centrale nei moderni protocolli di routing come OSPF nelle reti.
Quando usarlo
Applicare l'algoritmo di Dijkstra quando si cercano cammini minimi in grafi con pesi degli archi non negativi. È ideale per sistemi di navigazione, routing di rete e qualsiasi problema su grafo che richieda cammini ottimali. Usarlo per cammini minimi da sorgente singola a tutti i vertici. Per grafi con pesi negativi, usare Bellman-Ford. Per ricerca bidirezionale o guida euristica, considerare l'algoritmo A*.
Limiti e considerazioni
- Non può gestire grafi con pesi degli archi negativi
- Calcola i cammini minimi verso tutti i vertici, non solo una destinazione (sebbene possa terminare anticipatamente)
- Meno efficiente di A* quando sono disponibili informazioni euristiche
- Richiede la scoperta di tutti i vertici; inefficiente per connettività molto sparsa
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Semplice da capire e implementare con chiare garanzie di correttezza
- Efficiente con strutture dati appropriate: O((V+E)logV) con heap binario, O(V²) con array
- Ottimale per grafi con pesi non negativi; dimostra l'ottimalità dei cammini calcolati
- Funziona sia su grafi diretti che non diretti
- Fondamento per numerose estensioni e algoritmi correlati
Applicazioni
- Sistemi GPS e di navigazione: ricerca dei percorsi più brevi per veicoli e pedoni
- Protocolli di routing di rete: determinazione dei percorsi ottimali per pacchetti di dati nelle reti informatiche
- Reti sociali: ricerca dei percorsi di connessione più brevi tra utenti o influencer
- Sviluppo di videogiochi: pathfinding per intelligenza artificiale e movimento di personaggi non giocanti
- Pianificazione del movimento robotico: calcolo delle traiettorie ottimali per sistemi robotici
- Telecomunicazioni: ottimizzazione del routing delle chiamate e dei percorsi di propagazione del segnale
Come funziona
Come funziona
Impostare la distanza della sorgente a zero e tutte le altre distanze a infinito. Contrassegnare tutti i vertici come non visitati e creare una coda di priorità.
Selezionare il vertice non visitato con distanza minima dalla sorgente utilizzando la coda di priorità.
Per ogni vicino del vertice selezionato, se il cammino attraverso il vertice selezionato offre una distanza minore, aggiornare la distanza del vicino e aggiungerlo alla coda di priorità.
Errori comuni
- Utilizzo dell'algoritmo su grafi con pesi negativi, con conseguenti cammini minimi errati
- Implementazione inefficiente con operazione di estrazione minima in tempo lineare, che porta a scarse prestazioni
- Mancata corretta aggiornamento delle distanze quando i vicini vengono rivisitati attraverso cammini diversi
Domande frequenti
Perché l'algoritmo di Dijkstra fallisce con pesi negativi?
L'algoritmo presuppone che una volta che un vertice è finalizzato, non si possa trovare un cammino più breve attraverso vertici non visitati. Con pesi negativi, un cammino più lungo potrebbe successivamente migliorare quando viene utilizzato un arco negativo, violando questa assunzione.
Quale struttura dati dovrebbe essere utilizzata per la coda di priorità?
Gli heap binari forniscono operazioni O(logV) sia per l'inserimento che per l'estrazione, risultando in una complessità totale O((V+E)logV). Gli heap di Fibonacci raggiungono O(E+VlogV) ma hanno grandi fattori costanti. Gli array funzionano bene per grafi piccoli.
Come può l'algoritmo di Dijkstra trovare il cammino verso una destinazione specifica?
Terminare l'algoritmo non appena il vertice di destinazione viene selezionato (la sua distanza è finalizzata), evitando calcoli non necessari. In alternativa, ricostruire il cammino mantenendo puntatori padre durante l'esecuzione.
Può l'algoritmo di Dijkstra essere utilizzato in grafi non diretti?
Sì, i grafi non diretti possono essere rappresentati come grafi diretti con archi in entrambe le direzioni per ogni arco non diretto, ciascuno con lo stesso peso. L'algoritmo funziona in modo identico sulla rappresentazione bidirezionale.
Metodi correlati
Fonti
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Apri il riferimento DOICopiato.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copiato.