Oba pronalaze najkraće putanje iz izvora u ponderiranom grafu. Dijkstra je brža ali zahteva nenegativne težine; Bellman-Ford je sporija ali rukuje negativnim bridovima i detektuje negativne cikluse.
Ponovljeno proširi najbliži neposeteni čvor i relaksiraj njegove susedne čvorove.
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
Relaksiraj sve bridove V-1 puta; dalja relaksacija znači negativan ciklus.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Težine | nenegativne | bilo koje (uključujući negativne) |
| Vreme | O((V+E) log V) | O(V·E) |
| Neg. ciklus | n/a | detektuje ga |
Koristite Dijkstra po zadanoj postavci za nenegativne težine (mape, mreže). Koristite Bellman-Ford kada postoje negativni bridovi (npr. arbitraža). Dijkstra tiho prekida na negativnim težinama — klasična zamka.
Algoritmi najkraće putanje snabdevaju rutiranje, navigaciju, mrežne protokole i analizu troškova zavisnosti.
Znanje o ograničenju nenegativnih težina na Dijkstrinu sprečava pogrešne odgovore na terenu.
Ideja relaksacije povezuje pohlepno i DP razmišljanje, čineći je bogatom temom na visokom nivou.