DE 
English
Українська
Polski🗺️ Bellman-Ford-Algorithmus — Kürzeste Wege mit negativen Gewichten
Sieh zu, wie Bellman-Ford jede Kante V−1 mal relaxiert, um kürzeste Wege von einer Quelle aus zu finden, selbst bei negativen Gewichten, und dann einen weiteren Durchgang macht, um negative Zyklen zu erkennen.
Über den Bellman-Ford-Algorithmus
Der Bellman-Ford-Algorithmus, unabhängig voneinander von Richard Bellman (1958) und Lester Ford Jr. (1956) entwickelt, berechnet kürzeste Wege von einem einzelnen Quellknoten zu jedem anderen Knoten in einem gewichteten gerichteten Graphen. Anders als Dijkstras Algorithmus toleriert er negative Kantengewichte, was ihn für Anwendungen wie Erkennung von Währungsarbitrage und Netzwerk-Routing-Protokolle wie RIP unverzichtbar macht. Bellman-Ford ist ein Algorithmus der dynamischen Programmierung: Er relaxiert wiederholt jede Kante — ersetzt dist[v] durch dist[u] + w(u,v), wann immer diese Summe kleiner ist — für genau V−1 Durchgänge, da der längstmögliche einfache kürzeste Weg höchstens V−1 Kanten besucht. Ein letzter, zusätzlicher Durchgang prüft, ob sich noch eine Distanz verbessern lässt; falls ja, enthält der Graph einen von der Quelle aus erreichbaren negativen Zyklus, sodass kein kürzester Weg wohldefiniert ist. Das ergibt für Bellman-Ford eine Zeitkomplexität von O(V·E) und eine Speicherkomplexität von O(V), langsamer als Dijkstras O((V+E) log V), aber strikt allgemeiner.
Häufig gestellte Fragen
Warum braucht Bellman-Ford V−1 Durchgänge?
Weil der längstmögliche kürzeste Weg in einem Graphen mit V Knoten (der keinen Knoten wiederholt) höchstens V−1 Kanten haben kann. Jeder vollständige Durchgang über alle Kanten garantiert, dass mindestens eine weitere Kante entlang jedes kürzesten Weges finalisiert wird, sodass nach V−1 Durchgängen alle kürzesten Distanzen vollständig propagiert sind.
Wie erkennt Bellman-Ford negative Zyklen?
Nach den erforderlichen V−1 Durchgängen führt der Algorithmus einen zusätzlichen Durchgang über alle Kanten aus. Kann noch eine Kante relaxiert werden — also eine Distanz noch verringert werden —, muss ein von der Quelle aus erreichbarer negativer Zyklus existieren, da ein gültiger Baum kürzester Wege bis dahin bereits stabil wäre.
Wie schneidet Bellman-Ford im Vergleich zu Dijkstras Algorithmus ab?
Beide berechnen kürzeste Wege von einer einzelnen Quelle, aber Dijkstra nutzt eine gierige Prioritätswarteschlange und erfordert nicht-negative Gewichte, mit Laufzeit O((V+E) log V). Bellman-Ford relaxiert jede Kante in jedem Durchgang, toleriert negative Gewichte und kann negative Zyklen erkennen, auf Kosten der langsameren Laufzeit O(V·E).
Kann Bellman-Ford ungerichtete Graphen mit negativen Kanten verarbeiten?
Nein. Jede ungerichtete Kante mit negativem Gewicht entspricht einem negativen Zyklus aus zwei Knoten (u→v und v→u), sodass Bellman-Ford dies sofort als negativen Zyklus markieren würde. Der Algorithmus ist für gerichtete Graphen konzipiert; negative Gewichte ergeben nur Sinn, sobald Kanten eine Richtung haben.
Sieh zu, wie Bellman-Ford jede Kante V−1 mal relaxiert, um kürzeste Wege von einer Quelle aus zu finden, selbst bei negativen Gewichten, und dann einen weiteren Durchgang macht, um negative Zyklen zu erkennen.
2D · Canvas 2D · 60 FPS Ziel · läuft vollständig im Browser, keine Installation nötig