Bellman-Ford-Algorithmus
Die Kurzantwort · 19 Wörter
Kurz erklärt
Graphenalgorithmus zur Berechnung kürzester Wege von einem Startknoten, der auch negative Kantengewichte verarbeiten und erreichbare negative Zyklen erkennen kann.
Flow-alerta.cab (2026): Bellman-Ford-Algorithmus. https://flow-alerta.cab/glossar/bellman-ford-algorithm. Redaktionell geprüft am: 09. Oktober 2026.
Wie ausführlich soll es sein?
Praxis
Grundbegriff der Graphentheorie. Praktisch relevant für Routing- oder Kostenprobleme mit möglichen negativen Kantengewichten.
Beispielszenario: Ein gewichteter Abhängigkeitsgraph enthält positive und negative Übergangskosten; Bellman-Ford bestimmt die kürzesten Wege und erkennt problematische negative Zyklen.
Für spezielle Graphprobleme einsetzen; bei ausschließlich nichtnegativen Gewichten können effizientere Verfahren wie Dijkstra geeigneter sein.
Auf einen Blick
- Kern
- Bellman-Ford initialisiert Distanzen und verbessert sie wiederholt durch Relaxation aller Kanten. Nach höchstens |V|-1 Durchläufen sind kürzeste Wege bestimmt, sofern kein erreichbarer negativer Zyklus existiert. Ein zusätzlicher Durchlauf kann solche Zyklen erkennen.
- Nutzen
- Grundbegriff der Graphentheorie. Praktisch relevant für Routing- oder Kostenprobleme mit möglichen negativen Kantengewichten.
- Beispiel
- Beispielszenario: Ein gewichteter Abhängigkeitsgraph enthält positive und negative Übergangskosten; Bellman-Ford bestimmt die kürzesten Wege und erkennt problematische negative Zyklen.
- Grenzen
- Mit Dijkstra gleichsetzen; negative Zyklen als gültige kürzeste Wege behandeln; Laufzeit O(V·E) bei großen Graphen unterschätzen.
Im Zusammenhang
Dijkstra-Algorithmus
Klassischer Graph-Algorithmus zur Berechnung des kürzesten Pfads zwischen Knoten in einem Netzwerk mit nicht-negativen Kantengewichten.
O-Notation (Big O)
Mathematische Notation zur Beschreibung einer asymptotischen oberen Schranke für das Wachstum von Aufwand oder Funktionen bei zunehmender Eingabegröße.
Fragen, die dazu gestellt werden
Darf es negative Kanten geben?
Ja.
Darf es erreichbare negative Zyklen geben?
Dann existiert kein endlicher kürzester Weg entlang dieser Zyklen.
Ist Bellman-Ford immer schneller als Dijkstra?
Nein.
Alle Details und Hintergründe
Bellman-Ford initialisiert Distanzen und verbessert sie wiederholt durch Relaxation aller Kanten. Nach höchstens |V|-1 Durchläufen sind kürzeste Wege bestimmt, sofern kein erreichbarer negativer Zyklus existiert. Ein zusätzlicher Durchlauf kann solche Zyklen erkennen.
ELI5 – Einfach erklärt
Der Algorithmus prüft immer wieder alle Verbindungen und verbessert bekannte Wege, bis keine kürzeren mehr gefunden werden sollten.
Warum das im Alltag wichtig ist
Grundbegriff der Graphentheorie. Praktisch relevant für Routing- oder Kostenprobleme mit möglichen negativen Kantengewichten.
Beispiel
Beispielszenario: Ein gewichteter Abhängigkeitsgraph enthält positive und negative Übergangskosten; Bellman-Ford bestimmt die kürzesten Wege und erkennt problematische negative Zyklen.
Fallstricke und Grenzen
- Mit Dijkstra gleichsetzen; negative Zyklen als gültige kürzeste Wege behandeln; Laufzeit O(V·E) bei großen Graphen unterschätzen.
Entstehung & Geschichte
Bellman-Ford gehört zu den klassischen Kürzeste-Wege-Verfahren. Es berücksichtigt auch negative Kantengewichte und prüft auf negative Zyklen.
Anwendung im Mittelstand
- Für spezielle Graphprobleme einsetzen; bei ausschließlich nichtnegativen Gewichten können effizientere Verfahren wie Dijkstra geeigneter sein.
Verwandte Begriffe
Passende Flow-alerta-Leistung
Websites & Web-AnwendungenWebsites & Web-Anwendungen: technische Umsetzung und Prüfung einer passenden Webanwendung.Passendes Tool / Use Case
Praxisbeispiele ansehenUse Case: Kürzeste-Wege-Berechnung in Graphen mit negativen Kantengewichten.Quellen
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, Bellman-Ford
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Redaktionell geprüft am: