Beide finden kürzeste Pfade von einer Quelle in einem gewichteten Graphen. Dijkstra ist schneller, benötigt aber nicht-negative Gewichte; Bellman-Ford ist langsamer, verarbeitet aber negative Kanten und erkennt negative Zyklen.
Den nächsten unbesuchten Knoten wiederholt erweitern und seine Nachbarn entspannen.
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
Alle Kanten V-1 mal entspannen; weiteres Entspannen bedeutet einen negativen Zyklus.
| | Dijkstra | Bellman-Ford | |---|---------|| | Gewichte | nicht-negativ | beliebig (inkl. negativ) | | Zeit | O((V+E) log V) | O(V·E) | | Neg. Zyklus | n/a | erkennt ihn |
Verwenden Sie Dijkstra standardmäßig für nicht-negative Gewichte (Karten, Netzwerke). Verwenden Sie Bellman-Ford, wenn negative Kanten vorhanden sind (z. B. Arbitrage). Dijkstra bricht bei negativen Gewichten stillschweigend zusammen — eine klassische Falle.
Kürzeste-Pfad-Algorithmen treiben Routing, Navigation, Netzwerkprotokolle und Abhängigkeitskostenanalyse an.
Die Kenntnis der Nicht-Negativ-Gewicht-Einschränkung bei Dijkstra verhindert falsche Antworten in der Praxis.
Die Entspannungsidee verbindet gieriges und DP-Denken und macht dies zu einem reichhaltigen Senior-Level-Thema.