Floyd–Warshall-algoritmen
Gamle vejatlas havde en tabel bagerst: afstanden mellem hvert par af byer. Floyd–Warshall er en måde at beregne sådan en tabel på, og den er en af de korteste algoritmer, der nogensinde er skrevet: tre løkker, én sammenligning, og alle korteste afstande falder på plads.
Idéen
Dijkstras algoritme og Bellman–Ford finder de korteste afstande fra én start. Floyd–Warshall finder dem fra hver knude til hver anden knude på én gang, i en tabel med en række og en søjle pr. knude. Den starter med det, kanterne fortæller direkte, og forbedrer så hele tabellen ved at tillade flere og flere knuder som mellemstop på vejen.
Trin for trin
Udfyld tabellen: 0 fra hver knude til sig selv, kantens længde mellem naboer og uendelig ellers. Derefter, for hver knude k og for hvert par i, j: hvis afstanden fra i til k plus afstanden fra k til j er mindre end afstanden fra i til j, så skriv det mindre tal ind. Det er hele algoritmen. I kode er det tre løkker, med k yderst.
Et eksempel
Tag fire knuder med kanterne A–B med længde 3, B–C 1, A–C 5 og C–D 2. Tabellen starter med dem og med uendelig for A–D og B–D. Runde A ændrer intet, da enhver vej gennem A er længere. Runde B finder A til C via B: 3 + 1 = 4, kortere end 5. Runde C finder A til D via C: 4 + 2 = 6, og B til D: 1 + 2 = 3, begge de første veje, der er fundet. Runde D ændrer intet. Den endelige tabel: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.
Hvorfor løkkernes rækkefølge betyder noget
Mellemstoppet k skal være den yderste løkke. Efter runden for k er hvert felt den korteste afstand med kun de første k knuder som mellemstop, og den næste runde bygger videre på det: en bedste vej gennem det nye mellemstop er en bedste vej til det plus en bedste vej fra det, og begge er allerede rigtige. Lægges k i en indre løkke, forsvinder den garanti, og der kan stå forkerte afstande tilbage. Det er sikkert at opdatere tabellen undervejs i en runde, fordi k's egen række og søjle ikke ændres i den runde.
Historie og anvendelser
Bernard Roy beskrev metoden i 1959. I 1962 udgav Stephen Warshall den til transitiv lukning, som kun spørger, om én knude kan nå en anden, og Robert Floyd udgav den til korteste veje. Den beregner afstandstabeller og routingtabeller, finder et netværks diameter, fortæller, hvilke knuder der kan nå hvilke, og afslører med et negativt felt i diagonalen en negativ kreds.
Udforsk det
Åbn appen, og tryk på Trin. Grafen er på den ene side og tabellen på den anden. Hver runde fremhæver det aktuelle mellemstops række og søjle; hvert trin skriver ét pars kortere afstand og markerer de to felter, der blev lagt sammen. Felter, der er ændret i denne runde, er farvet. Vælg en start og et mål for at se den korteste vej mellem dem, når tabellen er færdig.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for Floyd–Warshall?
O(n³) for n knuder, uanset antallet af kanter, og O(n²) hukommelse til tabellen. Det er det oplagte valg til små eller tætte grafer, hvor den enkle løkke kører meget hurtigt.
Floyd–Warshall eller Dijkstra fra hver knude?
For en tæt graf, eller når kanter kan være negative, er Floyd–Warshall enklere og omtrent lige så hurtig. For en stor, tynd graf uden negative kanter er det hurtigere at køre Dijkstras algoritme fra hver knude.
Er Floyd–Warshall dynamisk programmering?
Ja. Den løser problemet for veje med mellemstop blandt de første k knuder ved hjælp af svarene for de første k − 1 knuder, og den holder kun én tabel, som den overskriver undervejs.
Hvad er transitiv lukning?
Tabellen over, hvilke knuder der kan nå hvilke, uden afstande. Warshalls version af algoritmen beregner den med "eller" og "og" i stedet for "min" og "+".
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv Floyd–Warshall