Ronde
Gewijzigd in deze ronde
Bekeken kanten

  • Huidig
  • Heeft een afstand
  • Gebruikte kant
  • Pad
  • Negatieve cyclus
Een klik op een knoop kiest

Meer over het Bellman–Ford-algoritme

Het Bellman–Ford-algoritme

Het algoritme van Dijkstra loopt vast als een kant een negatieve lengte heeft, zoals een weg die je tol betaalt in plaats van tol te vragen. Het Bellman–Ford-algoritme niet: het bekijkt gewoon elke kant steeds opnieuw tot er niets meer verbetert, en het merkt zelfs wanneer een cyclus de afstanden eindeloos laat dalen. Klik op een knoop om daar te beginnen en ga ronde voor ronde door het algoritme. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Elke kant is eenrichtingsverkeer, zoals de pijl laat zien, en het getal erop is de lengte, die negatief kan zijn. Klik op een knoop om die de start te maken; zet de klik op Doel en klik op een andere knoop om aan het eind het kortste pad ernaartoe te zien. Het getal op elke knoop is de afstand tot nu toe. Vink Negatieve cyclus toevoegen aan om te zien hoe Bellman–Ford er een vindt. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.

Hoe het werkt

  1. Klik op een knoop om die de start te maken. Wil je aan het eind een pad zien, zet de klik dan op Doel en klik op een andere knoop.
  2. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
  3. Vink Negatieve cyclus toevoegen aan om te zien hoe Bellman–Ford er een vindt. Nieuwe graaf maakt een andere graaf om te proberen.

Hoe Bellman–Ford werkt

Geef de start afstand 0 en elke andere knoop oneindig. Doe dan rondes: bekijk in elke ronde elke kant u → v één keer. Als u een afstand heeft en dist(u) plus de lengte van de kant korter is dan dist(v), verlaag dan dist(v) en onthoud u als de weg ernaartoe. Na ronde k is elk kortste pad met hoogstens k kanten bekend. Een kortste pad komt hoogstens één keer langs elke knoop, dus het heeft hoogstens n − 1 kanten, en n − 1 rondes zijn altijd genoeg. Verandert een hele ronde niets, dan kan het zoeken vroeg stoppen.

Een negatieve cyclus vinden

Tellen de kanten van een cyclus op tot minder dan nul, dan maakt nog een keer rond de cyclus een pad altijd korter, dus is er helemaal geen kortste pad. Bellman–Ford merkt dat: na n − 1 rondes zou nog een ronde niets mogen veranderen. Kan een kant toch nog worden gerelaxeerd, dan is er vanaf de start een negatieve cyclus te bereiken, en wie vanaf die kant de onthouden knopen terug volgt, komt erin terecht. In de app is de cyclus rood getekend.

Veelgestelde vragen

Wat is het Bellman–Ford-algoritme?

Een algoritme dat de kortste paden vindt van één start naar elke andere knoop in een graaf waarvan de kanten negatieve lengtes mogen hebben. Het relaxeert elke kant in herhaalde rondes en meldt een negatieve cyclus als die vanaf de start te bereiken is.

Waarom werkt het algoritme van Dijkstra niet met negatieve kanten?

Dijkstra maakt de afstand van een knoop definitief zodra die de dichtstbijzijnde in de wachtrij is. Een negatieve kant die later wordt gevonden, kan nog via een kortere weg naar die knoop terugleiden, dus de definitieve afstand kan fout zijn. Bellman–Ford maakt een afstand nooit vroeg definitief; het blijft elke kant bekijken.

Waarom n − 1 rondes?

Een kortste pad hoeft nooit twee keer langs een knoop te komen, dus het heeft hoogstens n − 1 kanten. Elke ronde verlengt de bekende kortste paden met minstens één kant, dus na n − 1 rondes zijn ze allemaal gevonden.

Hoe snel is Bellman–Ford?

Elke ronde bekijkt alle E kanten en er zijn hoogstens V − 1 rondes, dus het werk groeit met V × E. Dat is trager dan het algoritme van Dijkstra; daarom gebruik je Bellman–Ford als kanten negatief kunnen zijn.

Wordt mijn graaf ergens heen gestuurd?

Nee. De graaf wordt in je browser gemaakt en doorzocht, en je laatste instellingen blijven in de lokale opslag van deze browser.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Ga naar Editor