Complessità temporale e spaziale
Lezione 7 di 9 del corso Algoritmo di Dijkstra - Algoritmi su grafi di Coddy.
Complessità temporale:
- O(V2 + V*E) come scritto qui (ciascuno dei V passaggi analizza i vertici per trovare il minimo e gli archi per rilassarli). Con un heap binario e una lista di adiacenza, migliora a O((V + E) log V).
Complessità spaziale:
- O(V) per gli array delle distanze e dei vertici visitati (oltre agli archi di input).
Riepilogo:
- Dijkstra trova le distanze minime da una singola sorgente per pesi non negativi, finalizzando greedy il vertice più vicino e rilassandone gli archi.
- Non funziona con archi negativi; per quelli, usa Bellman-Ford.
Provalo tu
Questa lezione non include una sfida di codice.
Mettiti alla provaQuesta lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.
Tutte le lezioni di Algoritmo di Dijkstra - Algoritmi su grafi
2L'algoritmo
Come funziona?PseudocodiceImplementazione (Parte 1)Implementazione (Parte 2)
Complessità temporale e spazialeEsercitati da solo: Compilatore C online