Bellman-Ford en negatieve kanten
Negatieve gewichten verwerken en cycli detecteren
Bellman-Ford en negatieve kanten is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 3 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 Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wanneer Dijkstra faalt
Dijkstra vertrouwt erop dat een afstand die uit de heap is gehaald definitief is, maar een negatieve kant kan later een pad goedkoper maken. Daarom werkt het algoritme dan niet.
Bellman-Ford komt in beeld
Bellman-Ford verwerkt negatieve kantgewichten. Het is trager dan Dijkstra, maar betrouwbaar wanneer je niet op een gulzige aanpak kunt vertrouwen.
De belangrijkste bewerking
Het algoritme relaxeert steeds elke kant: als dist[u] plus het kantgewicht kleiner is dan dist[v], werk je dist[v] bij naar die kleinere waarde.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wHoeveel rondes zijn nodig
Een kortste pad gebruikt hoogstens V min 1 kanten, dus V-1 rondes waarin je elke kant relaxeert zijn genoeg om alle afstanden definitief vast te leggen.
for _ in range(n - 1):
relax_all_edges()Initialiseer de afstanden
Begin met elke afstand op oneindig, behalve de bron die op nul staat, precies zoals bij Dijkstra.
dist = [float('inf')] * n
dist[src] = 0Eén volledige ronde
Elke ronde doorloopt de volledige kantenlijst één keer en relaxeert elke kant. Verbeteringen verspreiden zich per ronde één sprong naar buiten.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wWaarom V-1 genoeg is
Na k rondes zijn alle kortste paden met k kanten correct. Na V-1 rondes is elk eenvoudig kortste pad voltooid.
De extra ronde
Voer nog één ronde uit. Als een afstand dan nog daalt, wordt iets steeds goedkoper, wat op een negatieve cyclus wijst.
Negatieve cycli detecteren
Een negatieve cyclus betekent dat er geen eindig kortste pad bestaat, omdat je eindeloos rond kunt gaan om de kosten zonder grens te verlagen.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'De uitvoeringstijd
Je relaxeert E kanten gedurende V rondes, dus Bellman-Ford draait in O(V * E), wat prima is voor kleine of middelgrote grafen.
Dijkstra of Bellman-Ford
Kies Dijkstra voor niet-negatieve gewichten en snelheid. Kies Bellman-Ford wanneer er negatieve gewichten voorkomen of je een slechte cyclus moet detecteren.
Snelle controle
Na V-1 rondes daalt een afstand tijdens nog een ronde. Wat betekent dat?
Samenvatting: Bellman-Ford
Relaxeer alle kanten gedurende V-1 rondes en voer daarna nog één ronde uit om negatieve cycli te detecteren. Het algoritme draait in O(V*E), maar werkt waar Dijkstra dat niet kan. ✅
Leer Python 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
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Bellman-Ford en negatieve kanten” gratis?
Ja — de volledige tekst van “Bellman-Ford en negatieve kanten” 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 Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Bellman-Ford en negatieve kanten”?
Negatieve gewichten verwerken en cycli detecteren Je oefent met Competitive Programming Academy 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 Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy 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 3 van 4.
Hoe lang duurt de les “Bellman-Ford en negatieve kanten”?
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 Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy 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 met een heap
- 0-1 BFS met een deque
- Bellman-Ford en negatieve kanten
- Floyd-Warshall voor alle paren