Dijkstras algoritm med en prioritetskö
Implementera Dijkstra med heapq, följ relaxeringsstegen i en viktad graf och lös cheapest-flights-within-k-stops.
Dijkstras algoritm med en prioritetskö är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Kortaste vägen i viktade grafer
Dijkstras algoritm hittar den kortaste vägen från en enda källnod till alla andra noder i en viktad graf med icke-negativa kantvikter. Den fungerar genom att girigt behandla noderna i ordning efter deras hittills bästa kända avstånd — den närmaste obesökta noden utvidgas alltid först. Den centrala datastrukturen är en min-heap (prioritetskö) som effektivt hämtar noden med det minsta avståndet.
Översikt över algoritmens steg
Dijkstras algoritm: (1) Initiera dist[source] = 0 och dist[all others] = inf. (2) Lägg (0, source) i en min-heap. (3) Ta bort noden u med det minsta avståndet. Om den redan har besökts med ett mindre avstånd hoppar ni över den. (4) För varje granne v till u: om dist[u] + weight(u,v) < dist[v], uppdatera dist[v] och lägg (dist[v], v) i heapen. (5) Upprepa tills heapen är tom.
Python-implementation med heapq
Pythons heapq implementerar en min-heap. Vi representerar grafen som en grannskapslista: graph[u] = [(v, weight), ...]. Heapens element är tupler av typen (distance, node). Vi använder en mängd visited för att hoppa över inaktuella poster i heapen — poster som lades in innan en bättre väg hittades.
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 distGenomräknat exempel
Betrakta en graf med 5 noder och kanterna: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). De kortaste vägarna från nod 0 är: till 1 via 0→2→1 med kostnaden 3, till 2 med kostnaden 1, till 3 via 0→2→1→3 med kostnaden 4 och till 4 via 0→2→1→3→4 med kostnaden 7. Dijkstra hittar alla dessa i en enda genomkörning, inte bara vägen till ett enskilt 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]Varför Dijkstra misslyckas med negativa vikter
Dijkstras korrekthet bygger på att en nods avstånd är slutgiltigt när noden tas ut ur min-heapen. Detta gäller bara om kantvikterna är icke-negativa. Med en negativ kant u→v med vikten -5 kan vi, efter att ha besökt v, hitta en kortare väg via u — men v är redan markerad som besökt. En enda negativ kant kan ogiltigförklara alla efterföljande avståndsberäkningar.
Billigaste flygresor med högst K stopp (LeetCode 787)
Det här problemet lägger till en begränsning: högst k stopp. Standardversionen av Dijkstra hanterar inte stegräkning direkt. Lösningen är att utöka tillståndet till (cost, node, stops_remaining). Använd Dijkstra med denna 3-tuppel, eller använd Bellman-Ford med k+1 relaxeringsomgångar. Den modifierade Dijkstra-algoritmen avbryter när stops_remaining når 0, vilket förhindrar fler hopp.
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)) # 200Analys av tidskomplexitet
Med en binär heap körs Dijkstra på O((V + E) log V) tid: varje hörn tas ut en gång (V uttag), varje kant kan utlösa en insättning (E insättningar), och varje heap-operation kostar O(log V). Med en Fibonacci-heap förbättras gränsen till O(E + V log V), men Pythons heapq är en binär heap. För glesa grafer (E ≈ V) är versionen med binär heap O(V log V); för täta grafer (E ≈ V²) är den O(V² log V).
Återskapa den kortaste vägen
Om ni vill återskapa den faktiska vägen, inte bara avstånden, använder ni en prev-array: när dist[v] uppdateras sätter ni prev[v] = u. När algoritmen är klar återskapar ni vägen från källa till mål genom att följa pekarna baklänges: börja vid dst, följ prev-pekare tills source nås och vänd sedan på resultatet.
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]Använda en dict för glesa grafer
När noderna är strängar eller icke-kontinuerliga heltal använder ni en defaultdict(list) som grannskapslista och en vanlig dict för avstånden. Detta är vanligt i LeetCode-problem som Network Delay Time, där noderna är numrerade från 1 till n. Kom ihåg att använda dist = {node: inf for node in all_nodes} och kontrollera om det finns oåtkomliga noder efter algoritmen.
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)) # 2Jämförelse med BFS för oviktade grafer
För oviktade grafer hittar BFS kortaste vägar på O(V + E) — snabbare än Dijkstras O((V+E) log V). Dijkstra generaliserar BFS till viktade grafer genom att använda en prioritetskö i stället för en vanlig FIFO-kö. När alla kantvikter är lika degenererar Dijkstra till BFS. Välj BFS för oviktade grafer, Dijkstra för icke-negativa vikter och Bellman-Ford för negativa vikter.
Dijkstra med optimeringen decrease-key
Läroboksvarianten av Dijkstra använder en prioritetskö med decrease-key: när en nods avstånd förbättras uppdateras dess prioritet direkt i kön. Detta kräver en Fibonacci-heap för O(E + V log V), men den är svår att implementera. Metoden med lazy deletion, som används i intervjuer, lägger i stället till en ny post och hoppar över föråldrade poster när de tas ut — enklare, med endast en konstantfaktor i extra kostnad. I Python är lazy deletion med heapq standardimplementeringen i intervjuer.
Snabbtest
Testa er förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen har ni lärt er: Dijkstra använder en min-heap för att girigt bearbeta noder i ordning efter deras aktuella bästa avstånd, algoritmen körs på O((V+E) log V) tid och fungerar inte med kanter med negativa vikter, och föråldrade poster i heapen hanteras genom att kontrollera en mängd med besökta noder när posterna tas ut. Härnäst går vi igenom Bellman-Ford, som hanterar negativa vikter genom n-1 relaxeringsomgångar.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Dijkstras algoritm med en prioritetskö” gratis?
Ja – hela texten till ”Dijkstras algoritm med en prioritetskö” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Dijkstras algoritm med en prioritetskö”?
Implementera Dijkstra med heapq, följ relaxeringsstegen i en viktad graf och lös cheapest-flights-within-k-stops. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Dijkstras algoritm med en prioritetskö”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Dijkstras algoritm med en prioritetskö
- Bellman-Ford och negativa cykler
- Floyd-Warshall: kortaste vägar mellan alla par
- Network Delay Time och återskapande av vägar