Bellman-Ford en negatieve cycli
Voer n-1 relaxatierondes uit over alle kanten, detecteer negatieve cycli met een laatste ronde en leg uit waarom Dijkstra faalt bij kanten met negatieve gewichten.
Bellman-Ford en negatieve cycli is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 2 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Waarom Bellman-Ford bestaat
Bellman-Ford lost het probleem van kortste paden vanaf één bron op, net als Dijkstra, maar kan ook overweg met negatieve gewichten van kanten. Het detecteert ook negatieve cycli — cycli waarvan het totale gewicht negatief is, waardoor het onmogelijk wordt om een eindig kortste pad erdoorheen te definiëren. Bellman-Ford is trager dan Dijkstra, maar is de juiste keuze wanneer de graaf negatieve gewichten van kanten kan bevatten.
Relaxatie: de kernbewerking
Bellman-Ford is gebaseerd op één bewerking: relaxatie. Een kant (u, v, w) relaxeren betekent: als dist[u] + w < dist[v], werk je dist[v] = dist[u] + w bij. We relaxeren herhaaldelijk alle kanten. Het belangrijkste inzicht is: elk kortste pad heeft hoogstens V-1 kanten (in een graaf zonder negatieve cycli). Daarom zijn V-1 rondes waarin je alle kanten relaxeert voldoende om alle kortste paden te vinden.
Bellman-Ford implementeren
Stel de graaf voor als een lijst van kanten [(u, v, weight)]. Initialiseer dist[source] = 0 en alle andere waarden met inf. Voer V-1 rondes uit en relaxeer in elke ronde alle kanten. Een bijwerking die nog in een V-de ronde plaatsvindt, wijst op een negatieve cyclus.
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]Waarom V-1 rondes voldoende zijn
Een kortste pad in een graaf zonder negatieve cycli bezoekt elke knoop hoogstens één keer en heeft daarom hoogstens V-1 kanten. Na ronde 1 zijn de kortste paden met één sprong optimaal. Na ronde 2 zijn de kortste paden met twee sprongen optimaal. Na V-1 rondes zijn alle kortste paden gevonden, omdat die hoogstens V-1 sprongen gebruiken. Als ronde V nog een afstand bijwerkt, bevat de graaf een negatieve cyclus die vanaf de bron bereikbaar is.
Negatieve cycli detecteren
Voer na V-1 rondes één extra ronde uit over alle kanten. Als een kant (u, v, w) voldoet aan dist[u] + w < dist[v], bestaat er een negatieve cyclus en is het kortste pad naar sommige knopen -infinity. Praktische toepassingen zijn onder andere het detecteren van arbitragemogelijkheden bij het wisselen van valuta (negatieve cycli in grafen met log-gewichten) en het detecteren van tegenstrijdigheden in beperkingssystemen.
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)) # TrueDijkstra en Bellman-Ford vergelijken
Dijkstra: O((V+E) log V), vereist niet-negatieve gewichten en gebruikt een hebzuchtige aanpak. Bellman-Ford: O(V × E), verwerkt negatieve gewichten en detecteert negatieve cycli. Voor de meeste sollicitatieopgaven met niet-negatieve gewichten heeft Dijkstra de voorkeur. Wanneer negatieve gewichten voorkomen (bijvoorbeeld bij 'vind het kortste pad met kanten met negatieve kosten' of 'detecteer arbitrage'), is Bellman-Ford het juiste antwoord. Voor dichte grafen is het slechtste geval O(V³) van Bellman-Ford vergelijkbaar met Floyd-Warshall.
Toepassing: goedkoopste vluchten met Bellman-Ford
Goedkoopste vluchten met maximaal K tussenstops (LeetCode 787) kan worden opgelost met een aangepaste versie van Bellman-Ford: voer precies k+1 relaxatierondes uit, omdat k tussenstops k+1 kanten betekenen. Gebruik een kopie van de afstanden uit de vorige ronde om te voorkomen dat we in één ronde meer sprongen gebruiken dan toegestaan — anders zou één ronde meerdere sprongen aan elkaar kunnen rijgen.
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)) # 200SPFA: optimalisatie met een wachtrij
Shortest Path Faster Algorithm (SPFA) is een geoptimaliseerde versie van Bellman-Ford die alleen kanten opnieuw relaxeert vanuit knopen waarvan de afstand zojuist is bijgewerkt, met behulp van een wachtrij. De complexiteit in het gemiddelde geval is O(E), maar in het slechtste geval blijft die O(V × E). SPFA is zelden nodig in sollicitatiegesprekken, maar je kunt het noemen als optimalisatie wanneer Bellman-Ford te traag is voor ijle grafen. Python heeft geen ingebouwde SPFA, maar je kunt die eenvoudig implementeren met collections.deque.
Valutaarbitrage detecteren
Een klassieke toepassing van Bellman-Ford: gegeven wisselkoersen, bepaal je of arbitrage mogelijk is (een cyclus waarin het omzetten van valuta meer oplevert dan je bent begonnen). Transformeer de wisselkoersen door de negatieve logaritme ervan te nemen. Arbitrage = een cyclus met een negatief totaal log-gewicht = een negatieve cyclus die Bellman-Ford kan detecteren. Zo worden financiële problemen uit de echte wereld vertaald naar het standaardalgoritme.
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 FalseOptimalisatie door vroegtijdig stoppen
Als in een volledige ronde over alle kanten geen enkele afstand wordt bijgewerkt, zullen latere rondes ook niets meer bijwerken — stop dan vroegtijdig. Deze optimalisatie verlaagt de complexiteit in het beste geval naar O(E), wanneer de graaf na enkele rondes al optimaal is. Voeg aan het begin van elke ronde een vlag updated = False toe; als die na de ronde nog steeds False is, breek je onmiddellijk af.
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 distBellman-Ford op grafen met adjacentielijsten
Wanneer de graaf wordt gegeven als een adjacentielijst in plaats van een lijst van kanten, zet je die eerst om naar een lijst van kanten of doorloop je alle vermeldingen in de adjacentielijst als kanten. Voor V=1000 en E=5000 betekenen V-1=999 rondes waarin 5000 kanten worden doorlopen 4.995.000 bewerkingen — ruim binnen de tijdslimieten. Voor zeer dichte grafen (E ≈ V²) komt het slechtste geval O(V³) overeen met Floyd-Warshall, waardoor de keuze afhankelijk is van de context.
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 distKorte toets
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: Bellman-Ford relaxeert alle kanten V-1 keer om kanten met negatieve gewichten te verwerken, een V-de relaxatieronde waarin nog verbeteringen worden gevonden, wijst op een negatieve cyclus en het algoritme werkt in O(V × E), tegenover O((V+E) log V) voor Dijkstra. Hierna behandelen we Floyd-Warshall voor kortste paden tussen alle paren in één berekening van O(V³).
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Bellman-Ford en negatieve cycli” gratis?
Ja — de volledige tekst van “Bellman-Ford en negatieve cycli” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Bellman-Ford en negatieve cycli”?
Voer n-1 relaxatierondes uit over alle kanten, detecteer negatieve cycli met een laatste ronde en leg uit waarom Dijkstra faalt bij kanten met negatieve gewichten. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Bellman-Ford en negatieve cycli”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Dijkstra's algoritme met een priority queue
- Bellman-Ford en negatieve cycli
- Floyd-Warshall: kortste paden tussen alle paren
- Network Delay Time en padreconstructie