Tussenstop
Ingekorte paren
Bekeken paren

  • Huidige tussenstop
  • Al een tussenstop
  • Ingekort paar
  • Pad
Een klik op een knoop kiest

Meer over het Floyd–Warshall-algoritme

Floyd–Warshall-algoritme

Hoe ver is het van elke stad naar elke andere stad? Floyd–Warshall beantwoordt dat in één keer, met een tabel en drie geneste lussen. Elke ronde staat één knoop meer toe als tussenstop en vraagt voor elk paar of de omweg erlangs korter is. Ga stap voor stap om de tabel te zien vullen en de afstanden te zien dalen. Druk op Afspelen om de tabel te zien vullen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. De tabel bevat de kortste afstand tot nu toe tussen elk paar knopen; het getal op elke kant is de lengte. Elke ronde staat één knoop meer toe als tussenstop onderweg, en elke stap toont een paar dat daardoor korter wordt. 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 ertussen te zien. 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. Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
  2. Volg de tabel: de rij en kolom van de huidige tussenstop zijn gekleurd, en elke stap schrijft een kortere afstand.
  3. Kies een start en een doel om aan het eind het kortste pad ertussen te zien. Nieuwe graaf maakt een andere graaf om te proberen.

Zo werkt Floyd–Warshall

Maak een tabel met één rij en één kolom per knoop. Vul 0 in op de diagonaal, de lengte van de kant waar twee knopen verbonden zijn, en overal anders oneindig. Neem dan elke knoop k om de beurt als mogelijke tussenstop. Vergelijk voor elk paar i, j de afstand van i naar j in de tabel met de afstand van i naar k plus de afstand van k naar j, en houd de kleinste. Na de laatste knoop is elk vakje de kortste afstand tussen zijn twee knopen.

Waarom het werkt

Na de ronde van k bevat de tabel voor elk paar het kortste pad waarvan alle tussenstops bij de knopen horen die al aan de beurt waren. De ronde van de volgende knoop hoeft alleen te beslissen of die knoop helpt: een kortste pad erlangs is een kortste pad ernaartoe plus een kortste pad ervandaan, en die staan allebei al in de tabel. Een groot antwoord zo opbouwen uit kleinere die al gevonden zijn, heet dynamisch programmeren. Met negatieve kanten werkt het nog steeds, en een negatief getal op de diagonaal verraadt een negatieve cyclus.

Veelgestelde vragen

Wat is het Floyd–Warshall-algoritme?

Een algoritme dat de kortste afstand vindt tussen elk paar knopen in een gewogen graaf. Het houdt een tabel met afstanden bij en kijkt voor elke knoop om de beurt of een weg via die knoop een paar korter maakt.

Hoe snel is Floyd–Warshall?

Het heeft drie geneste lussen over de n knopen, dus het werk groeit met n³, en de tabel heeft n² vakjes nodig. Dat gaat prima voor grafen van een paar honderd knopen. Voor grote, ijle grafen is het sneller om het algoritme van Dijkstra vanaf elke knoop uit te voeren.

Kan Floyd–Warshall negatieve kanten aan?

Ja, zolang er geen negatieve cyclus is. Als er een is, wordt een vakje op de diagonaal negatief, en zo ontdekt Floyd–Warshall die.

Hoe krijg ik de paden, niet alleen de afstanden?

Houd een tweede tabel bij met de volgende knoop op de weg van i naar j. Telkens als een paar korter wordt via k, neem je de volgende knoop van i richting k over. Volg die tabel van i naar j, en je hebt het pad.

Wordt mijn graaf ergens heen gestuurd?

Nee. De graaf wordt in je browser gemaakt en de tabel wordt er gevuld, 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