Mindkettő a legrövidebb utakat egy forrásból keresi meg egy súlyozott gráfban. A Dijkstra gyorsabb, de nem-negatív súlyokat igényel; a Bellman-Ford lassabb, de negatív éleket kezel és negatív ciklusokat detektál.
Ismételten bővítsd a legközelebbi nem látogatott csomópontot és relaxáld szomszédait.
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
Relaxáld az összes élt V-1 alkalommal; további relaxáció negatív ciklust jelent.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Súlyok | nem-negatív | bármilyen (negatívot is beleértve) |
| Idő | O((V+E) log V) | O(V·E) |
| Neg. ciklus | n/a | detektálja |
Használd az Dijkstrát alapértelmezésben nem-negatív súlyokhoz (térképek, hálózatok). Használd a Bellman-Fordot, ha negatív élek vannak jelen (pl. arbitrázskereskedelem). A Dijkstra csendesen megtörik a negatív súlyoknál — klasszikus csapda.
A legrövidebb út algoritmusok a routing, a navigáció, a hálózati protokollok és a függőség költségelemzést működtetik.
A Dijkstra nem-negatív súlykorlátjának ismerete megelőzi a helytelen válaszokat a gyakorlatban.
A relaxáció ötlete összeköti a greedy és a DP gondolkodást, ami gazdag senior szintű témává teszi.