Oba znajdują najkrótsze ścieżki ze źródła w grafie ważonym. Dijkstra jest szybsza, ale wymaga wag niedosmemnych; Bellman-Ford jest wolniejszy, ale obsługuje krawędzie ujemne i wykrywa cykle ujemne.
Zachłannie rozszerzaj najbliższy nieodwiedzony wierzchołek i relaksuj jego sąsiadów.
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
Relaksuj wszystkie krawędzie V-1 razy; dalsze relaksacje oznaczają cykl ujemny.
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Wagi | niedosmemne | dowolne (w tym ujemne) |
| Czas | O((V+E) log V) | O(V·E) |
| Cykl ujemny | n/d | je wykrywa |
Używaj Dijkstry domyślnie dla wag niedosmemnych (mapy, sieci). Używaj Bellman-Ford gdy istnieją ujemne krawędzie (np. arbitraż). Dijkstra cicho psuje się na ujemnych wagach — klasyczne pułapka.
Algorytmy najkrótszej ścieżki zasilają routing, nawigację, protokoły sieciowe i analizę kosztów zależności.
Znajomość ograniczenia wag niedosmemnych w Dijkstrze zapobiega błędnym odpowiedziom w praktyce.
Idea relaksacji łączy myślenie zachłanne i DP, czyniąc to bogatym tematem na poziomie seniora.