Dijkstras algoritme med en prioritetskø
Implementér Dijkstra med heapq, gennemgå afslapningstrinnene på en vægtet graf, og løs cheapest-flights-within-k-stops.
Dijkstras algoritme med en prioritetskø er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Korteste vej i vægtede grafer
Dijkstras algoritme finder den korteste vej fra en enkelt kildeknude til alle andre knuder i en vægtet graf med ikke-negative kantvægte. Den fungerer ved grådigt at behandle knuder i rækkefølge efter deres hidtil bedste kendte afstand — den udvider altid den nærmeste ubesøgte knude. Den centrale datastruktur er en min-heap (prioritetskø), som effektivt finder den knude, der har den mindste afstand.
Oversigt over algoritmens trin
Dijkstras algoritme: (1) Initialisér dist[source] = 0 og dist[all others] = inf. (2) Læg (0, source) i en min-heap. (3) Fjern knuden u med den mindste afstand. Hvis den allerede er besøgt med en mindre afstand, springer du over den. (4) For hver nabo v til u: Hvis dist[u] + weight(u,v) < dist[v], skal du opdatere dist[v] og lægge (dist[v], v) i heapen. (5) Gentag, indtil heapen er tom.
Implementering i Python med heapq
Pythons heapq implementerer en min-heap. Vi repræsenterer grafen som en naboliste: graph[u] = [(v, weight), ...]. Heap'en gemmer tupler på formen (distance, node). Vi bruger en visited-mængde til at springe over forældede poster i heapen — poster, der blev lagt i heapen, før en bedre vej blev fundet.
import heapq
def dijkstra(graph, source):
n = len(graph)
dist = [float('inf')] * n
dist[source] = 0
heap = [(0, source)] # (distance, node)
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(heap, (dist[v], v))
return distGennemarbejdet eksempel
Betragt en graf med 5 knuder og kanterne: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Korteste veje fra knude 0: til 1 via 0→2→1 koster 3, til 2 koster 1, til 3 via 0→2→1→3 koster 4, og til 4 via 0→2→1→3→4 koster 7. Dijkstra finder alle disse på én gennemløbning, ikke kun vejen til et enkelt mål.
import heapq
def dijkstra(graph, source):
dist = [float('inf')] * len(graph)
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = [
[(1,4),(2,1)], # 0
[(3,1)], # 1
[(1,2),(3,5)], # 2
[(4,3)], # 3
[] # 4
]
print(dijkstra(graph, 0)) # [0, 3, 1, 4, 7]Hvorfor Dijkstra fejler med negative vægte
Dijkstras korrekthed bygger på, at en nodes afstand er fastlagt, så snart noden tages ud af min-heapen. Det gælder kun, hvis kantvægtene er ikke-negative. Med en negativ kant u→v med vægten -5 kan vi efter at have besøgt v finde en kortere sti gennem u — men v er allerede markeret som besøgt. Én negativ kant kan ugyldiggøre alle efterfølgende afstandsberegninger.
Billigste flyrejser med højst K stop (LeetCode 787)
Dette problem tilføjer en begrænsning: højst k stop. Standard-Dijkstra håndterer ikke antallet af trin direkte. Løsning: udvid tilstanden til (cost, node, stops_remaining). Brug Dijkstra med denne 3-tupel, eller brug Bellman-Ford med k+1 relaksationsrunder. Den modificerede Dijkstra stopper, når stops_remaining når 0, så yderligere hop forhindres.
import heapq
from collections import defaultdict
def findCheapestPrice(n, flights, src, dst, k):
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, k + 1)] # (cost, node, hops_left)
visited = {} # node -> min hops_left seen at this cost level
while heap:
cost, node, hops = heapq.heappop(heap)
if node == dst:
return cost
if hops == 0:
continue
if visited.get(node, 0) >= hops:
continue
visited[node] = hops
for nxt, w in graph[node]:
heapq.heappush(heap, (cost + w, nxt, hops - 1))
return -1
print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200Analyse af tidskompleksitet
Med en binær heap kører Dijkstra på O((V + E) log V)-tid: hver knude tages ud én gang (V udtagninger), hver kant kan udløse en indsættelse (E indsættelser), og hver heap-operation koster O(log V). Med en Fibonacci-heap forbedres grænsen til O(E + V log V), men Pythons heapq er en binær heap. For sparsomme grafer (E ≈ V) er versionen med binær heap O(V log V); for tætte grafer (E ≈ V²) er den O(V² log V).
Genskabelse af den korteste sti
For at genskabe den faktiske sti (ikke kun afstandene) skal du vedligeholde en prev-liste: Når du opdaterer dist[v], skal du sætte prev[v] = u. Når algoritmen er færdig, genskaber du stien fra kilde til destination ved at gå baglæns: Start ved dst, følg prev-pegerne, indtil du når source, og vend derefter resultatet om.
import heapq
def dijkstra_path(graph, source, target):
n = len(graph)
dist = [float('inf')] * n
prev = [-1] * n
dist[source] = 0
heap = [(0, source)]
visited = set()
while heap:
d, u = heapq.heappop(heap)
if u in visited: continue
visited.add(u)
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
heapq.heappush(heap, (dist[v], v))
# Reconstruct
path, node = [], target
while node != -1:
path.append(node)
node = prev[node]
return dist[target], path[::-1]Brug af en ordbog til sparsomme grafer
Når noder er strenge eller ikke-sammenhængende heltal, skal du bruge en defaultdict(list) til nabolisten og en almindelig dict til afstande. Det er almindeligt i LeetCode-opgaver som Network Delay Time, hvor noderne er nummereret fra 1 til n. Husk at bruge dist = {node: inf for node in all_nodes} og kontrollere, om der findes utilgængelige noder, efter algoritmen er kørt.
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
ans = max(dist.values())
return ans if ans < float('inf') else -1
print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)) # 2Sammenligning med BFS for uvægtede grafer
For uvægtede grafer finder BFS korteste stier i O(V + E) — hurtigere end Dijkstras O((V+E) log V). Dijkstra generaliserer BFS til vægtede grafer ved at bruge en prioritetskø i stedet for en almindelig FIFO-kø. Når alle kantvægte er ens, degenererer Dijkstra til BFS. Vælg BFS til uvægtede grafer, Dijkstra til ikke-negative vægte og Bellman-Ford til negative vægte.
Dijkstra med optimering med decrease-key
Den klassiske Dijkstra-algoritme bruger en prioritetskø med decrease-key: Når en nodes afstand bliver mindre, opdateres dens prioritet direkte. Det kræver en Fibonacci-heap for O(E + V log V), men er svært at implementere. Tilgangen med doven sletning, som bruges til tekniske jobsamtaler, indsætter i stedet en ny post og springer forældede udtagninger over — enklere med kun en konstant faktor i ekstra tidsforbrug. I Python er doven sletning med heapq standardimplementeringen til tekniske jobsamtaler.
Hurtigt tjek
Afprøv din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion har du lært: Dijkstra bruger en min-heap til grådigt at behandle noder i rækkefølge efter deres aktuelt bedste afstand, den kører i O((V+E) log V)-tid og fejler på kanter med negative vægte, og forældede heap-poster håndteres ved at kontrollere en mængde af besøgte noder, når de tages ud. Næste emne er Bellman-Ford, som håndterer negative vægte gennem n-1 relaksationsrunder.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Dijkstras algoritme med en prioritetskø” gratis?
Ja — hele teksten til “Dijkstras algoritme med en prioritetskø” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Dijkstras algoritme med en prioritetskø”?
Implementér Dijkstra med heapq, gennemgå afslapningstrinnene på en vægtet graf, og løs cheapest-flights-within-k-stops. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Dijkstras algoritme med en prioritetskø”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Dijkstras algoritme med en prioritetskø
- Bellman-Ford og negative cykler
- Floyd-Warshall: Korteste veje mellem alle par
- Netværksforsinkelse og rekonstruktion af sti