Het Floyd–Warshall-algoritme

Oude wegenatlassen hadden achterin een tabel: de afstand tussen elk paar steden. Floyd–Warshall is een manier om zo'n tabel te berekenen, en het is een van de kortste algoritmen ooit geschreven: drie lussen, één vergelijking, en elke kortste afstand valt op zijn plek.

Een kleine graaf waarvan de kanten lengtes hebben, naast een tabel met afstanden tussen elk paar knopen, met één rij en één kolom gemarkeerd
Een kleine graaf waarvan de kanten lengtes hebben, naast een tabel met afstanden tussen elk paar knopen, met één rij en één kolom gemarkeerd

Het idee

Het algoritme van Dijkstra en Bellman–Ford vinden de kortste afstanden vanaf één start. Floyd–Warshall vindt ze in één keer van elke knoop naar elke andere knoop, in een tabel met een rij en een kolom per knoop. Het begint met wat de kanten direct vertellen, en verbetert dan de hele tabel door steeds meer knopen toe te staan als tussenstop onderweg.

Stap voor stap

Vul de tabel: 0 van elke knoop naar zichzelf, de lengte van de kant tussen buren, en elders oneindig. Dan, voor elke knoop k en elk paar i, j: als de afstand van i naar k plus de afstand van k naar j kleiner is dan de afstand van i naar j, schrijf dan het kleinere getal in. Dat is het hele algoritme. In code zijn het drie lussen, met k als buitenste.

Een voorbeeld

Neem vier knopen met de kanten A–B met lengte 3, B–C 1, A–C 5 en C–D 2. De tabel begint daarmee, en met oneindig voor A–D en B–D. Ronde A verandert niets, want elke weg via A is langer. Ronde B vindt A naar C via B: 3 + 1 = 4, korter dan 5. Ronde C vindt A naar D via C: 4 + 2 = 6, en B naar D: 1 + 2 = 3, allebei de eerste weg die gevonden is. Ronde D verandert niets. De uiteindelijke tabel: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Waarom de volgorde van de lussen ertoe doet

De tussenstop k moet de buitenste lus zijn. Na de ronde van k is elk vakje de kortste afstand met alleen de eerste k knopen als tussenstop, en de volgende ronde bouwt daarop voort: een beste pad via de nieuwe tussenstop is een beste pad ernaartoe plus een beste pad ervandaan, en die kloppen allebei al. Met k in een binnenste lus vervalt die garantie en kunnen er verkeerde afstanden overblijven. De tabel tijdens een ronde ter plekke bijwerken is veilig, want de rij en kolom van k zelf veranderen in die ronde niet.

Geschiedenis en toepassingen

Bernard Roy beschreef de methode in 1959. In 1962 publiceerde Stephen Warshall haar voor de transitieve afsluiting, die alleen vraagt of een knoop een andere kan bereiken, en Robert Floyd voor kortste paden. Ze berekent afstandstabellen en routeringstabellen, vindt de diameter van een netwerk, vertelt welke knopen welke kunnen bereiken, en verraadt met een negatief vakje op de diagonaal een negatieve cyclus.

Probeer het zelf

Open de app en druk op Stap. De graaf staat aan de ene kant en de tabel aan de andere. Elke ronde markeert de rij en kolom van de huidige tussenstop; elke stap schrijft de kortere afstand van één paar in en omlijnt de twee vakjes die zijn opgeteld. Vakjes die in deze ronde veranderd zijn, zijn gekleurd. Kies een start en een doel om het kortste pad ertussen te zien als de tabel af is.

Veelgestelde vragen

Wat is de tijdcomplexiteit van Floyd–Warshall?

O(n³) voor n knopen, ongeacht het aantal kanten, en O(n²) geheugen voor de tabel. Het is de aangewezen methode voor kleine of dichte grafen, waar de eenvoudige lus heel snel loopt.

Floyd–Warshall of Dijkstra vanaf elke knoop?

Voor een dichte graaf, of als kanten negatief kunnen zijn, is Floyd–Warshall eenvoudiger en ongeveer even snel. Voor een grote, ijle graaf zonder negatieve kanten is het sneller om het algoritme van Dijkstra vanaf elke knoop uit te voeren.

Is Floyd–Warshall dynamisch programmeren?

Ja. Het lost het probleem op voor paden met tussenstops uit de eerste k knopen met de antwoorden voor de eerste k − 1 knopen, en houdt maar één tabel bij, die het onderweg overschrijft.

Wat is transitieve afsluiting?

De tabel van welke knopen welke kunnen bereiken, zonder afstanden. Warshalls versie van het algoritme berekent die met "of" en "en" in plaats van "min" en "+".

Klaar om het te proberen?

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

Probeer Floyd–Warshall