Dijkstra med en heap
Grådige korteste stier på kanter uten negative vekter
Dijkstra med en heap er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Problemet med korteste vei
Du ønsker den billigste ruten fra én node til alle andre noder. Dijkstra løser dette når alle kantvekter er null eller positive.
Den grådige idéen
Dijkstra er grådig: Algoritmen utvider alltid den ubesøkte noden med den minste kjente avstanden og stoler på at denne avstanden er endelig.
Hvorfor en min-heap
For å hente den nærmeste noden raskt trenger du en min-heap. Den gir deg den minste avstanden på log n-tid i stedet for et langsomt søk gjennom alle.
import heapqStart med avstander
Sett alle avstander til uendelig, og sett deretter startnoden til null. Noder som ikke nås, blir stående som uendelige for alltid.
dist = [float('inf')] * n
dist[src] = 0Legg startnoden i heapen
Legg startnoden inn som en tuppel med (avstand, node). Når avstanden står først, kan heapen automatisk sortere oppføringene etter kostnad.
pq = [(0, src)]Ta ut den nærmeste noden
I hver iterasjon tar du ut den minste (d, u) med pop. Da er d den korteste avstanden til u, så arbeidet med u er ferdig.
d, u = heapq.heappop(pq)Hopp over foreldede oppføringer
En node kan ligge i heapen med en gammel og større avstand. Hopp over den når d er større enn den lagrede avstanden.
if d > dist[u]:
continueRelakser naboene
Relaksasjon betyr å prøve å forbedre en nabo: Hvis det er billigere å gå via u, oppdaterer du avstanden og legger naboen i heapen.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Trikset med lat sletting
Python-heapen kan ikke oppdatere en nøkkel, så du legger inn duplikater og ignorerer foreldede oppføringer. Denne late metoden holder koden kort og rask.
Kjøretiden
Med en binær heap bruker Dijkstra O((V + E) log V). Det håndterer enkelt grafer med hundretusener av kanter.
Følg med på kantvektene
Dijkstra fungerer ikke med negative kanter, fordi en avstand som er tatt ut av heapen, kanskje ikke er endelig. Bruk Bellman-Ford i stedet.
Hurtigsjekk
Du tar ut (d, u), men d er større enn dist[u]. Hva bør du gjøre?
Oppsummering: Dijkstra med heap
Du initialiserer avstandene, legger inn (dist, node), tar ut den nærmeste, hopper over foreldede oppføringer og relakserer naboene. Det er Dijkstra i O((V+E) log V). 🚀
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Dijkstra med en heap» gratis?
Ja – hele teksten i «Dijkstra med en heap» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Dijkstra med en heap»?
Grådige korteste stier på kanter uten negative vekter Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Dijkstra med en heap»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Dijkstra med en heap
- 0-1 BFS med en deque
- Bellman-Ford og negative kanter
- Floyd-Warshall for alle par