Floyd–Warshall-algoritmen

Gamla vägatlaser hade en tabell längst bak: avståndet mellan varje par av städer. Floyd–Warshall är ett sätt att räkna fram en sådan tabell, och den är en av de kortaste algoritmer som någonsin skrivits: tre loopar, en jämförelse, och alla kortaste avstånd faller på plats.

En liten graf vars kanter har längder, bredvid en tabell med avstånd mellan varje par av noder, med en rad och en kolumn markerade
En liten graf vars kanter har längder, bredvid en tabell med avstånd mellan varje par av noder, med en rad och en kolumn markerade

Idén

Dijkstras algoritm och Bellman–Ford hittar de kortaste avstånden från en start. Floyd–Warshall hittar dem från varje nod till varje annan nod på en gång, i en tabell med en rad och en kolumn per nod. Den börjar med det kanterna säger direkt och förbättrar sedan hela tabellen genom att tillåta fler och fler noder som mellanstopp på vägen.

Steg för steg

Fyll i tabellen: 0 från varje nod till sig själv, kantens längd mellan grannar och oändligt annars. Sedan, för varje nod k och för varje par i, j: om avståndet från i till k plus avståndet från k till j är mindre än avståndet från i till j, skriv in det mindre talet. Det är hela algoritmen. I kod är det tre loopar, med k ytterst.

Ett exempel

Ta fyra noder med kanterna A–B med längd 3, B–C 1, A–C 5 och C–D 2. Tabellen börjar med dem, och oändligt för A–D och B–D. Runda A ändrar inget, eftersom varje väg genom A är längre. Runda B hittar A till C via B: 3 + 1 = 4, kortare än 5. Runda C hittar A till D via C: 4 + 2 = 6, och B till D: 1 + 2 = 3, båda de första vägarna som hittats. Runda D ändrar inget. Den slutliga tabellen: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Varför loopordningen spelar roll

Mellanstoppet k måste vara den yttersta loopen. Efter rundan för k är varje ruta det kortaste avståndet med bara de första k noderna som mellanstopp, och nästa runda bygger på det: en bästa väg genom det nya mellanstoppet är en bästa väg dit plus en bästa väg därifrån, och båda stämmer redan. Läggs k i en inre loop försvinner den garantin, och felaktiga avstånd kan bli kvar. Att uppdatera tabellen på plats under en runda är säkert, eftersom k:s egen rad och kolumn inte ändras i den rundan.

Historia och användning

Bernard Roy beskrev metoden 1959. År 1962 publicerade Stephen Warshall den för transitivt hölje, som bara frågar om en nod kan nå en annan, och Robert Floyd publicerade den för kortaste vägar. Den räknar fram avståndstabeller och routingtabeller, hittar ett nätverks diameter, visar vilka noder som kan nå vilka och avslöjar med en negativ ruta på diagonalen en negativ cykel.

Utforska

Öppna appen och tryck på Steg. Grafen finns på ena sidan och tabellen på den andra. Varje runda markerar det aktuella mellanstoppets rad och kolumn; varje steg skriver ett pars kortare avstånd och ramar in de två rutor som lades ihop. Rutor som ändrats i den här rundan är färgade. Välj en start och ett mål för att se den kortaste vägen mellan dem när tabellen är klar.

Ofta ställda frågor

Vilken tidskomplexitet har Floyd–Warshall?

O(n³) för n noder, oavsett antalet kanter, och O(n²) minne för tabellen. Det är det självklara valet för små eller täta grafer, där den enkla loopen går mycket snabbt.

Floyd–Warshall eller Dijkstra från varje nod?

För en tät graf, eller när kanter kan vara negativa, är Floyd–Warshall enklare och ungefär lika snabb. För en stor gles graf utan negativa kanter är det snabbare att köra Dijkstras algoritm från varje nod.

Är Floyd–Warshall dynamisk programmering?

Ja. Den löser problemet för vägar med mellanstopp bland de första k noderna med hjälp av svaren för de första k − 1 noderna, och håller bara en tabell, som den skriver över allteftersom.

Vad är transitivt hölje?

Tabellen över vilka noder som kan nå vilka, utan avstånd. Warshalls version av algoritmen räknar fram den med "eller" och "och" i stället för "min" och "+".

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova Floyd–Warshall