Motivation
Lektion 2 von 9 im Kurs Bellman-Ford-Algorithmus - Graphenalgorithmen von Coddy.
Bellman-Ford basiert auf einer Operation, der Relaxierung: Für eine Kante u -> v mit dem Gewicht w wird dist[v] aktualisiert, wenn der Weg über u günstiger ist (dist[u] + w < dist[v]). Dies wird für jede Kante wiederholt durchgeführt.
Warum Bellman-Ford lernen?
- Negative Gewichte: Er funktioniert dort, wo Dijkstra versagt, zum Beispiel bei Kosten, die Rabatte oder Währungsarbitrage darstellen können.
- Erkennung negativer Zyklen: Ein zusätzlicher Relaxierungsdurchlauf deckt Zyklen auf, deren Gesamtgewicht negativ ist.
- Einfachheit: Keine Prioritätswarteschlange, nur wiederholte Kantenrelaxierung.
Der Kompromiss liegt in der Geschwindigkeit: O(V * E), was langsamer ist als Dijkstras O((V + E) log V).
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
