Oba nacházejí nejkratší cesty ze zdroje v orientovaném grafu se záporami. Dijkstra je rychlejší, ale vyžaduje nezáporné váhy; Bellman-Ford je pomalejší, ale zvládá záporné hrany a detekuje negativní cykly.
Opakovaně rozšiřuj nejbližší nenavštívený uzel a relaxuj jeho sousedy.
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
Relaxuj všechny hrany V-1 krát; další relaxace znamená záporný cyklus.
| | Dijkstra | Bellman-Ford | |---|---------|| | Váhy | nezáporné | jakékoli (včetně záporných) | | Čas | O((V+E) log V) | O(V·E) | | Záporný cyklus | nepoužívá se | detekuje jej |
Pro nezáporné váhy používej Dijkstru standardně (mapy, sítě). Když existují záporné hrany, použij Bellman-Ford (např. arbitráž). Dijkstra tiše selhává u záporných vah — klasická past.
Algoritmy nejkratší cesty pohánějí směrování, navigaci, síťové protokoly a analýzu nákladů závislostí.
Znalost omezení nezáporné váhy na Dijkstrovi brání špatným odpovědím v praxi.
Myšlenka relaxace spojuje hladový přístup a dynamické programování, čímž je toto bohaté téma na úrovni seniora.