Mellemstop
Forkortede par
Undersøgte par

  • Aktuelt mellemstop
  • Allerede mellemstop
  • Forkortet par
  • Vej
Et klik på en knude sætter

Mere om Floyd–Warshall-algoritmen

Floyd–Warshall-algoritmen

Hvor langt er der fra hver by til hver anden by? Floyd–Warshall svarer på det i ét hug, med en tabel og tre indlejrede løkker. Hver runde tillader én knude mere som mellemstop og spørger for hvert par, om omvejen gennem den er kortere. Gå trin for trin igennem, og se tabellen blive udfyldt og afstandene falde. Tryk på Afspil for at se tabellen blive udfyldt, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Tabellen indeholder den korteste afstand indtil nu mellem hvert par af knuder; tallet på hver kant er dens længde. Hver runde tillader én knude mere som mellemstop på vejen, og hvert trin viser et par, der bliver kortere gennem den. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at se den korteste vej mellem dem til sidst. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst.
  2. Følg tabellen: det aktuelle mellemstops række og søjle er farvet, og hvert trin skriver en kortere afstand.
  3. Vælg en start og et mål for at se den korteste vej mellem dem til sidst. Ny graf laver en anden graf, du kan prøve.

Sådan virker Floyd–Warshall

Lav en tabel med én række og én søjle pr. knude. Skriv 0 i diagonalen, kantens længde, hvor to knuder er forbundet, og uendelig alle andre steder. Tag så hver knude k efter tur som muligt mellemstop. For hvert par i, j sammenlignes tabellens afstand fra i til j med afstanden fra i til k plus afstanden fra k til j, og den mindste beholdes. Efter den sidste knude er hvert felt den korteste afstand mellem sine to knuder.

Hvorfor det virker

Efter runden for k indeholder tabellen for hvert par den korteste vej, hvis mellemstop alle er blandt de knuder, der er klaret indtil nu. Runden for den næste knude skal kun afgøre, om den knude hjælper: en korteste vej gennem den er en korteste vej til den plus en korteste vej fra den, og begge står allerede i tabellen. At bygge et stort svar af mindre svar, der allerede er fundet, kaldes dynamisk programmering. Med negative kanter virker det stadig, og et negativt tal i diagonalen afslører en negativ kreds.

Ofte stillede spørgsmål

Hvad er Floyd–Warshall-algoritmen?

En algoritme, der finder den korteste afstand mellem hvert par af knuder i en vægtet graf. Den holder en tabel med afstande og undersøger for hver knude efter tur, om en vej gennem den knude gør et par kortere.

Hvor hurtig er Floyd–Warshall?

Den har tre indlejrede løkker over de n knuder, så arbejdet vokser med n³, og tabellen kræver n² felter. Det går fint for grafer med et par hundrede knuder. For store, tynde grafer er det hurtigere at køre Dijkstras algoritme fra hver knude.

Kan Floyd–Warshall håndtere negative kanter?

Ja, så længe der ikke er nogen negativ kreds. Er der en, bliver et felt i diagonalen negativt, og sådan opdager Floyd–Warshall den.

Hvordan får jeg vejene og ikke kun afstandene?

Hold en anden tabel med den næste knude på vejen fra i til j. Hver gang et par bliver kortere via k, kopierer du den næste knude fra i mod k. Følg den tabel fra i til j, så får du vejen.

Bliver min graf sendt nogen steder hen?

Nej. Grafen laves, og tabellen udfyldes i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor