Begge finner korteste stier fra en kilde i en vektet graf. Dijkstra er raskere, men krever ikke-negative vekter; Bellman-Ford er langsommere, men håndterer negative kanter og oppdager negative sykler.
Utvid gjentatt den nærmeste ubesøkte noden og slipp av naboene dens.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
Slipp av alle kanter V-1 ganger; ytterligere slipping betyr en negativ syklus.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Vekter | ikke-negative | hvilke som helst (inkludert negative) |
| Tid | O((V+E) log V) | O(V·E) |
| Neg. syklus | n/a | oppdager det |
Bruk Dijkstra som standard for ikke-negative vekter (kart, nettverk). Bruk Bellman-Ford når negative kanter eksisterer (f.eks. arbitrage). Dijkstra brytes stille på negative vekter — en klassisk felle.
Korteste-sti-algoritmer driver ruting, navigasjon, nettverksprotokoller og analyser av avhengighetskostnader.
Å kjenne ikke-negativ-vektbegrensningen på Dijkstra forhindrer feil svar i praksis.
Avslapningsideen forbinder grådig og DP-tenking, noe som gjør det til et rikt seniorempirisk emne.