0Pricing
DSA Interview Prep · Lektion

Bellman-Ford und negative Zyklen

Führen Sie n-1 Relaxierungsdurchläufe über alle Kanten aus, erkennen Sie negative Zyklen mit einem abschließenden Durchlauf und erklären Sie, warum Dijkstra bei Kanten mit negativem Gewicht versagt.

Bellman-Ford und negative Zyklen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 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 DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Warum es Bellman-Ford gibt

Bellman-Ford löst wie Dijkstra das Problem der kürzesten Wege von einer Quelle aus, verarbeitet jedoch auch negative Kantengewichte. Außerdem erkennt es negative Zyklen – Zyklen, deren Gesamtgewicht negativ ist, sodass kein endlicher kürzester Pfad durch sie definiert werden kann. Bellman-Ford ist zwar langsamer als Dijkstra, aber immer dann die richtige Wahl, wenn der Graph Kanten mit negativen Gewichten enthalten kann.

Relaxierung: Die zentrale Operation

Bellman-Ford basiert auf einer einzigen Operation: der Relaxierung. Die Relaxierung der Kante (u, v, w) bedeutet: Wenn dist[u] + w < dist[v], aktualisieren Sie dist[v] = dist[u] + w. Wir relaxieren wiederholt alle Kanten. Die entscheidende Erkenntnis lautet: Jeder kürzeste Pfad hat höchstens V-1 Kanten (in einem Graphen ohne negative Zyklen). Daher reichen V-1 Relaxierungsrunden über alle Kanten aus, um alle kürzesten Pfade zu finden.

Bellman-Ford-Implementierung

Stellen Sie den Graphen als Kantenliste [(u, v, weight)] dar. Initialisieren Sie dist[source] = 0 und alle anderen Werte mit inf. Führen Sie V-1 Runden durch und relaxieren Sie in jeder Runde alle Kanten. Jede Aktualisierung, die noch in einer V-ten Runde erfolgt, weist auf einen negativen Zyklus hin.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

Warum V-1 Durchläufe ausreichen

Ein kürzester Pfad in einem Graphen ohne negative Zyklen besucht jeden Knoten höchstens einmal und hat daher höchstens V-1 Kanten. Nach Runde 1 sind die kürzesten Pfade mit einem Sprung optimal. Nach Runde 2 sind die kürzesten Pfade mit zwei Sprüngen optimal. Nach V-1 Runden wurden alle kürzesten Pfade gefunden, die höchstens V-1 Sprünge verwenden. Wenn Runde V eine Distanz weiterhin aktualisiert, enthält der Graph einen vom Ausgangsknoten aus erreichbaren negativen Zyklus.

Erkennung negativer Zyklen

Führen Sie nach V-1 Durchläufen einen zusätzlichen Durchlauf über alle Kanten aus. Wenn eine Kante (u, v, w) die Bedingung dist[u] + w < dist[v] erfüllt, existiert ein negativer Zyklus und der kürzeste Pfad zu einigen Knoten ist -infinity. Zu den Anwendungen in der Praxis gehören das Erkennen von Arbitragegelegenheiten im Währungshandel (negative Zyklen in Graphen mit logarithmierten Gewichten) und das Erkennen von Inkonsistenzen in Constraint-Systemen.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

Dijkstra und Bellman-Ford im Vergleich

Dijkstra: O((V+E) log V), erfordert nichtnegative Gewichte, Greedy-Ansatz. Bellman-Ford: O(V × E), verarbeitet negative Gewichte und erkennt negative Zyklen. Für die meisten Interviewaufgaben mit nichtnegativen Gewichten wird Dijkstra bevorzugt. Wenn negative Gewichte auftreten (z. B. „kürzesten Pfad mit Kanten mit negativen Kosten finden“ oder „Arbitrage erkennen“), ist Bellman-Ford die richtige Wahl. Für dichte Graphen ist Bellman-Fords Worst Case O(V³) mit Floyd-Warshall vergleichbar.

Anwendung: Günstigste Flüge mit Bellman-Ford

Cheapest Flights Within K Stops (LeetCode 787) lässt sich mit einer modifizierten Version von Bellman-Ford lösen: Führen Sie genau k+1 Relaxierungsdurchläufe aus (da k Zwischenstopps k+1 Kanten bedeuten). Verwenden Sie eine Kopie der Distanzen aus dem vorherigen Durchlauf, um sicherzustellen, dass wir in einem einzelnen Durchlauf nicht mehr Sprünge als erlaubt verwenden – andernfalls könnte ein einzelner Durchlauf mehrere Sprünge hintereinander verketten.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA: Optimierung mit Warteschlange

Shortest Path Faster Algorithm (SPFA) ist eine optimierte Version von Bellman-Ford, die mithilfe einer Warteschlange nur die Kanten von Knoten erneut relaxiert, deren Distanz gerade aktualisiert wurde. Im Durchschnitt beträgt die Komplexität O(E), im Worst Case bleibt sie jedoch bei O(V × E). SPFA wird in Interviews nur selten benötigt, aber Sie können den Algorithmus als Optimierung erwähnen, wenn Bellman-Ford bei dünn besetzten Graphen zu langsam ist. Python verfügt nicht über eine integrierte SPFA-Implementierung, aber mit collections.deque lässt sie sich unkompliziert umsetzen.

Erkennung von Währungsarbitrage

Eine klassische Anwendung von Bellman-Ford: Ermitteln Sie anhand von Wechselkursen, ob Arbitrage möglich ist (ein Zyklus, bei dem die Umrechnung mehr zurückgibt, als Sie ursprünglich eingesetzt haben). Transformieren Sie die Wechselkurse, indem Sie ihren negativen Logarithmus nehmen. Arbitrage = ein Zyklus mit negativem Gesamtgewicht der Logarithmen = ein negativer Zyklus, den Bellman-Ford erkennen kann. So lassen sich reale Finanzprobleme auf den Standardalgorithmus abbilden.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

Optimierung durch vorzeitigen Abbruch

Wenn in einem vollständigen Durchlauf über alle Kanten keine Distanz aktualisiert wird, werden auch nachfolgende Durchläufe nichts ändern – beenden Sie den Algorithmus vorzeitig. Diese Optimierung reduziert die Komplexität im besten Fall auf O(E), wenn der Graph bereits nach wenigen Durchläufen optimal ist. Fügen Sie am Anfang jedes Durchlaufs ein Flag updated = False hinzu; bleibt es nach dem Durchlauf False, brechen Sie sofort ab.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

Bellman-Ford auf Graphen mit Adjazenzlisten

Wenn der Graph als Adjazenzliste statt als Kantenliste gegeben ist, konvertieren Sie ihn zunächst in eine Kantenliste oder iterieren Sie über alle Einträge der Adjazenzliste und behandeln Sie sie als Kanten. Für V=1000 und E=5000 ergeben V-1=999 Durchläufe mit jeweils 5000 geprüften Kanten 4,995,000 Operationen – deutlich innerhalb der Zeitlimits. Für sehr dichte Graphen (E ≈ V²) entspricht der Worst Case O(V³) dem von Floyd-Warshall, sodass die Wahl vom jeweiligen Kontext abhängt.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Schnelltest

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

Zusammenfassung der Lektion

In dieser Lektion haben Sie gelernt: Bellman-Ford relaxiert alle Kanten V-1-mal, um Kanten mit negativen Gewichten zu verarbeiten, ein V-ter Relaxierungsdurchlauf, der weiterhin Verbesserungen findet, weist auf einen negativen Zyklus hin und der Algorithmus hat die Komplexität O(V × E) im Vergleich zu Dijkstras O((V+E) log V). Als Nächstes behandeln wir Floyd-Warshall für kürzeste Wege zwischen allen Knotenpaaren in einer einzigen Berechnung mit O(V³).

Häufig gestellte Fragen

Ist die Lektion „Bellman-Ford und negative Zyklen“ kostenlos?

Ja — der vollständige Text von „Bellman-Ford und negative Zyklen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Bellman-Ford und negative Zyklen“?

Führen Sie n-1 Relaxierungsdurchläufe über alle Kanten aus, erkennen Sie negative Zyklen mit einem abschließenden Durchlauf und erklären Sie, warum Dijkstra bei Kanten mit negativem Gewicht versagt. Du übst DSA 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 DSA Interview Prep zu starten?

Keine Vorkenntnisse erforderlich. DSA 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 2 von 4.

Wie lange dauert die Lektion „Bellman-Ford und negative Zyklen“?

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 DSA Interview Prep-Lektion Code schreiben und ausführen?

Ja. Jede DSA 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

  1. Dijkstras Algorithmus mit einer Priority Queue
  2. Bellman-Ford und negative Zyklen
  3. Floyd-Warshall: Kürzeste Wege zwischen allen Knotenpaaren
  4. Network Delay Time und Pfadrekonstruktion
← Zurück zu DSA Interview Prep