Beiden vinden kortste paden vanaf een bron in een gewogen graaf. Dijkstra is sneller maar vereist niet-negatieve gewichten; Bellman-Ford is langzamer maar verwerkt negatieve randen en detecteert negatieve cycles.
Breid herhaaldelijk het dichtst nabije niet-bezochte knooppunt uit en relaxeer zijn buren.
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
Relaxeer alle randen V-1 keer; verdere relaxatie betekent een negatieve cycle.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Gewichten | niet-negatief | elk (inclusief negatief) |
| Tijd | O((V+E) log V) | O(V·E) |
| Neg. cycle | n.v.t. | detecteert het |
Gebruik standaard Dijkstra voor niet-negatieve gewichten (kaarten, netwerken). Gebruik Bellman-Ford wanneer negatieve randen voorkomen (bijv. arbitrage). Dijkstra faalt stilzwijgend bij negatieve gewichten — een klassieke valkuil.
Kortste-padalgoritmen voeden routing, navigatie, netwerkprotocollen en afhankelijkheidskostenanalyse.
De niet-negatieve-gewichtbeperking van Dijkstra kennen voorkomt foutieve antwoorden in praktijk.
Het relaxatie-idee verbindt gierige en DP-denken, waardoor het een rijk onderwerp op senior-niveau is.
Een bibliotheek met IT-sollicitatievragen met gedetailleerde antwoorden — van Junior tot Senior.
Doneren