Durchlauf
In diesem Durchlauf geändert
Geprüfte Kanten

  • Aktuell
  • Hat einen Abstand
  • Genutzte Kante
  • Weg
  • Negativer Zyklus
Ein Klick auf einen Knoten setzt

Mehr über den Bellman–Ford-Algorithmus

Bellman–Ford-Algorithmus

Der Dijkstra-Algorithmus versagt, wenn eine Kante eine negative Länge hat, wie eine Straße, auf der man Maut bekommt, statt sie zu zahlen. Der Bellman–Ford-Algorithmus nicht: Er prüft einfach jede Kante immer wieder, bis sich nichts mehr verbessert, und er erkennt sogar, wenn ein Zyklus die Abstände endlos sinken lässt. Klicken Sie auf einen Knoten, um dort zu beginnen, und gehen Sie die Durchläufe Schritt für Schritt durch. Drücken Sie Abspielen, um der Suche zuzusehen, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Jede Kante führt nur in eine Richtung, wie ihr Pfeil zeigt, und die Zahl darauf ist ihre Länge, die negativ sein kann. Klicken Sie auf einen Knoten, um ihn zum Start zu machen; stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten, um am Ende den kürzesten Weg dorthin zu sehen. Die Zahl auf jedem Knoten ist sein bisheriger Abstand. Aktivieren Sie Negativen Zyklus hinzufügen, um zu sehen, wie Bellman–Ford einen findet. Neuer Graph erzeugt einen anderen Graphen; wählen Sie, wie viele Knoten und Kanten er hat. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.

Wie es funktioniert

  1. Klicken Sie auf einen Knoten, um ihn zum Start zu machen. Um am Ende einen Weg zu sehen, stellen Sie den Klick auf Ziel um und klicken Sie auf einen anderen Knoten.
  2. Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück schrittweise vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
  3. Aktivieren Sie Negativen Zyklus hinzufügen, um zu sehen, wie Bellman–Ford einen findet. Neuer Graph erzeugt einen anderen Graphen zum Ausprobieren.

So funktioniert Bellman–Ford

Geben Sie dem Start den Abstand 0 und allen anderen Knoten unendlich. Dann folgen Durchläufe: In jedem Durchlauf wird jede Kante u → v einmal geprüft. Hat u einen Abstand und ist dist(u) plus die Länge der Kante kürzer als dist(v), senken Sie dist(v) und merken Sie sich u als Weg dorthin. Nach Durchlauf k ist jeder kürzeste Weg mit höchstens k Kanten bekannt. Ein kürzester Weg besucht jeden Knoten höchstens einmal, hat also höchstens n − 1 Kanten, und n − 1 Durchläufe reichen immer. Ändert ein ganzer Durchlauf nichts, kann die Suche früh aufhören.

Einen negativen Zyklus finden

Ergeben die Kanten eines Zyklus zusammen weniger als null, macht jede weitere Runde durch ihn einen Weg kürzer, also gibt es gar keinen kürzesten Weg. Bellman–Ford merkt das: Nach n − 1 Durchläufen dürfte ein weiterer Durchlauf nichts mehr ändern. Lässt sich noch eine Kante relaxieren, ist vom Start aus ein negativer Zyklus erreichbar, und wenn man von dieser Kante aus den gemerkten Knoten zurück folgt, gelangt man in ihn hinein. In der App ist der Zyklus rot gezeichnet.

Häufig gestellte Fragen

Was ist der Bellman–Ford-Algorithmus?

Ein Algorithmus, der die kürzesten Wege von einem Start zu allen anderen Knoten in einem Graphen findet, dessen Kanten negative Längen haben dürfen. Er relaxiert jede Kante in wiederholten Durchläufen und meldet einen negativen Zyklus, wenn einer vom Start aus erreichbar ist.

Warum scheitert der Dijkstra-Algorithmus bei negativen Kanten?

Dijkstra macht den Abstand eines Knotens endgültig, sobald er der nächstgelegene in der Warteschlange ist. Eine später gefundene negative Kante kann aber noch auf einem kürzeren Weg zu diesem Knoten zurückführen, sodass der endgültige Abstand falsch sein kann. Bellman–Ford macht keinen Abstand zu früh endgültig; er prüft immer weiter jede Kante.

Warum n − 1 Durchläufe?

Ein kürzester Weg muss keinen Knoten zweimal besuchen, hat also höchstens n − 1 Kanten. Jeder Durchlauf verlängert die bekannten kürzesten Wege um mindestens eine Kante, also sind nach n − 1 Durchläufen alle gefunden.

Wie schnell ist Bellman–Ford?

Jeder Durchlauf prüft alle E Kanten, und es gibt höchstens V − 1 Durchläufe, also wächst der Aufwand mit V × E. Das ist langsamer als der Dijkstra-Algorithmus, darum nimmt man Bellman–Ford dann, wenn Kanten negativ sein können.

Wird mein Graph irgendwohin gesendet?

Nein. Der Graph wird in Ihrem Browser erzeugt und durchsucht, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor