Dijkstra con un heap
Trovare cammini minimi greedy su archi non negativi
Dijkstra con un heap è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il problema del cammino minimo
Si desidera trovare il percorso meno costoso da un nodo a tutti gli altri. Dijkstra risolve questo problema quando ogni peso degli archi è zero o positivo.
L'idea greedy
Dijkstra è greedy: espande sempre il nodo non visitato con la distanza conosciuta più piccola, assumendo che tale distanza sia definitiva.
Perché usare un min-heap
Per recuperare rapidamente il nodo più vicino serve un min-heap. Restituisce la distanza minima in tempo log n, invece di richiedere una scansione lenta.
import heapqIniziare dalle distanze
Imposti ogni distanza a infinito, quindi imposti a zero quella della sorgente. I nodi non raggiunti rimangono semplicemente a infinito per sempre.
dist = [float('inf')] * n
dist[src] = 0Inizializzare l'heap
Inserisca la sorgente come tupla di (distance, node). Mettendo prima la distanza, l'heap ordina automaticamente le voci in base al costo.
pq = [(0, src)]Estrarre il nodo più vicino
A ogni iterazione, esegua il pop del minimo (d, u). Quella d è la distanza minima da u, quindi il suo processamento è concluso una volta estratta.
d, u = heapq.heappop(pq)Ignorare le voci obsolete
Un nodo può trovarsi nell'heap con una distanza vecchia e maggiore. Lo ignori quando d è peggiore della distanza memorizzata.
if d > dist[u]:
continueRilassare i vicini
Il rilassamento consiste nel provare a migliorare la distanza di un vicino: se passare da u è più conveniente, aggiorni la sua distanza e lo inserisca nell'heap.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))La tecnica della cancellazione lazy
Gli heap di Python non possono aggiornare una chiave, quindi si inseriscono duplicati e si ignorano quelli obsoleti. Questo approccio lazy mantiene il codice breve e veloce.
Il tempo di esecuzione
Con un heap binario, Dijkstra richiede O((V + E) log V). Gestisce facilmente grafi con centinaia di migliaia di archi.
Attenzione ai pesi degli archi
Dijkstra non funziona con archi negativi, perché una distanza estratta potrebbe non essere definitiva. In questi casi, utilizzi Bellman-Ford.
Verifica rapida
Estrae (d, u), ma d è maggiore di dist[u]. Che cosa dovrebbe fare?
Riepilogo: Dijkstra con un heap
Inizializzi le distanze, inserisca (dist, node), estragga il nodo più vicino, ignori le estrazioni obsolete e rilassi i vicini. Questo è Dijkstra in O((V+E) log V). 🚀
Domande Frequenti
La lezione «Dijkstra con un heap» è gratuita?
Sì — il testo completo di «Dijkstra con un heap» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Dijkstra con un heap»?
Trovare cammini minimi greedy su archi non negativi Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Dijkstra con un heap»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Dijkstra con un heap
- BFS 0-1 con una Deque
- Bellman-Ford e archi negativi
- Floyd-Warshall per tutte le coppie