Bellman-Ford und negative Kanten
Behandeln Sie negative Gewichte und erkennen Sie Zyklen
Bellman-Ford und negative Kanten ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Wenn Dijkstra scheitert
Dijkstra geht davon aus, dass eine entnommene Entfernung endgültig ist. Eine negative Kante kann einen Weg jedoch später noch günstiger machen. Deshalb scheitert der Algorithmus.
Bellman-Ford kommt ins Spiel
Bellman-Ford verarbeitet negative Kantengewichte. Der Algorithmus ist langsamer als Dijkstra, aber auch dort zuverlässig, wo man der Greedy-Logik nicht vertrauen kann.
Die zentrale Operation
Der Algorithmus relaxiert wiederholt jede Kante: Wenn dist[u] plus das Kantengewicht kleiner als dist[v] ist, aktualisieren Sie dist[v] auf diesen kleineren Wert.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wWie viele Runden
Ein kürzester Weg verwendet höchstens V minus 1 Kanten. Daher reichen V-1 Runden, in denen alle Kanten relaxiert werden, um alle Entfernungen festzulegen.
for _ in range(n - 1):
relax_all_edges()Entfernungen initialisieren
Setzen Sie wie bei Dijkstra jede Entfernung auf Unendlich, außer der des Startknotens, die Sie auf null setzen.
dist = [float('inf')] * n
dist[src] = 0Ein vollständiger Durchlauf
In jedem Durchlauf wird die gesamte Kantenliste einmal durchlaufen und jede Kante relaxiert. Verbesserungen breiten sich pro Durchlauf um eine Kante weiter aus.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wWarum V-1 ausreicht
Nach k Durchläufen sind alle kürzesten Wege mit k Kanten korrekt. Nach V-1 Durchläufen ist jeder einfache kürzeste Weg vollständig berücksichtigt.
Der zusätzliche Durchlauf
Führen Sie einen weiteren Durchlauf aus. Wenn eine Entfernung dabei noch kleiner wird, wird etwas weiterhin günstiger – ein Hinweis auf einen negativen Zyklus.
Negative Zyklen erkennen
Ein negativer Zyklus bedeutet, dass kein endlicher kürzester Weg existiert, weil Sie die Kosten durch beliebig häufiges Durchlaufen ohne Grenze weiter senken können.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'Die Laufzeit
Sie relaxieren E Kanten über V Durchläufe. Daher läuft Bellman-Ford in O(V * E) und eignet sich für kleine oder mittelgroße Graphen.
Dijkstra oder Bellman-Ford
Wählen Sie Dijkstra bei nicht negativen Gewichten und wenn Geschwindigkeit wichtig ist. Wählen Sie Bellman-Ford bei negativen Gewichten oder wenn Sie einen problematischen Zyklus erkennen müssen.
Schnelltest
Nach V-1 Durchläufen wird eine Entfernung in einem weiteren Durchlauf noch kleiner. Was bedeutet das?
Zusammenfassung: Bellman-Ford
Relaxieren Sie alle Kanten in V-1 Durchläufen und anschließend ein weiteres Mal, um negative Zyklen zu erkennen. Der Algorithmus läuft in O(V*E), funktioniert aber auch dort, wo Dijkstra scheitert. ✅
Häufig gestellte Fragen
Ist die Lektion „Bellman-Ford und negative Kanten“ kostenlos?
Ja — der vollständige Text von „Bellman-Ford und negative Kanten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bellman-Ford und negative Kanten“?
Behandeln Sie negative Gewichte und erkennen Sie Zyklen Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Bellman-Ford und negative Kanten“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Dijkstra mit einem Heap
- 0-1 BFS mit einer Deque
- Bellman-Ford und negative Kanten
- Floyd-Warshall für alle Paare