- Aktuellt mellanstopp
- Redan mellanstopp
- Förkortat par
- Väg
Floyd–Warshall-algoritmen
Hur långt är det från varje stad till varje annan stad? Floyd–Warshall svarar på det i ett svep, med en tabell och tre nästlade loopar. Varje runda tillåter en nod till som mellanstopp och frågar för varje par om omvägen genom den är kortare. Gå steg för steg och se tabellen fyllas i och avstånden sjunka. Tryck på Spela för att se tabellen fyllas i, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Tabellen innehåller det kortaste avståndet hittills mellan varje par av noder; talet på varje kant är dess längd. Varje runda tillåter en nod till som mellanstopp på vägen, och varje steg visar ett par som blir kortare genom den. Klicka på en nod för att göra den till start; byt klicket till Mål och klicka på en annan nod för att se den kortaste vägen mellan dem i slutet. Ny graf skapar en annan graf; välj hur många noder och kanter den har. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.
Hur det fungerar
- Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
- Följ tabellen: det aktuella mellanstoppets rad och kolumn är färgade, och varje steg skriver ett kortare avstånd.
- Välj en start och ett mål för att se den kortaste vägen mellan dem i slutet. Ny graf skapar en annan graf att prova.
Så fungerar Floyd–Warshall
Gör en tabell med en rad och en kolumn per nod. Fyll i 0 på diagonalen, kantens längd där två noder är förbundna och oändligt överallt annars. Ta sedan varje nod k i tur och ordning som möjligt mellanstopp. För varje par i, j jämförs tabellens avstånd från i till j med avståndet från i till k plus avståndet från k till j, och det minsta behålls. Efter sista noden är varje ruta det kortaste avståndet mellan sina två noder.
Varför det fungerar
Efter rundan för k innehåller tabellen för varje par den kortaste vägen vars mellanstopp alla finns bland noderna som hanterats hittills. Rundan för nästa nod behöver bara avgöra om den noden hjälper: en kortaste väg genom den är en kortaste väg dit plus en kortaste väg därifrån, och båda finns redan i tabellen. Att bygga ett stort svar av mindre svar som redan hittats kallas dynamisk programmering. Med negativa kanter fungerar det fortfarande, och ett negativt tal på diagonalen avslöjar en negativ cykel.
Ofta ställda frågor
Vad är Floyd–Warshall-algoritmen?
En algoritm som hittar det kortaste avståndet mellan varje par av noder i en viktad graf. Den håller en tabell med avstånd och kontrollerar för varje nod i tur och ordning om en väg genom den noden gör något par kortare.
Hur snabb är Floyd–Warshall?
Den har tre nästlade loopar över de n noderna, så arbetet växer med n³, och tabellen behöver n² rutor. Det går bra för grafer med några hundra noder. För stora glesa grafer är det snabbare att köra Dijkstras algoritm från varje nod.
Klarar Floyd–Warshall negativa kanter?
Ja, så länge det inte finns någon negativ cykel. Om det finns en blir någon ruta på diagonalen negativ, och så upptäcker Floyd–Warshall den.
Hur får jag vägarna och inte bara avstånden?
Håll en andra tabell med nästa nod på vägen från i till j. Varje gång ett par blir kortare via k kopierar du nästa nod från i mot k. Följ den tabellen från i till j, så får du vägen.
Skickas min graf någonstans?
Nej. Grafen skapas och tabellen fylls i i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor