- Aktuell
- I kön
- Slutgiltiga
- Väg
Dijkstras algoritm
Dijkstras algoritm hittar den kortaste vägen från en start till alla andra noder när kanterna har längder, som vägar mellan städer. Den växer utåt från starten och tar alltid den närmaste nod den inte är klar med än. Klicka på en nod för att starta från den, välj ett mål om du vill, och stega igenom för att se kön, se varje avstånd sjunka när kortare vägar dyker upp och se den kortaste vägen träda fram. Tryck på Spela för att se sökningen, 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. 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 söka en kortaste väg dit. Talet på varje kant är dess längd, talet på varje nod dess kortaste avstånd hittills, och raden under grafen är kön, närmaste först. 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
- Klicka på en nod för att göra den till start. Vill du söka en väg, byt klicket till Mål och klicka på en annan nod.
- 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 i sökningen.
- Följ kön under grafen och avståndet på varje nod. Ny graf skapar en annan graf att prova.
Så fungerar Dijkstras algoritm
Ge starten avstånd 0 och alla andra noder oändligt, och lägg starten i en kö. Upprepa sedan: ta den nod i kön som har minst avstånd och gör avståndet slutgiltigt. För varje granne som inte är slutgiltig, lägg till kantens längd till nodens avstånd. Är summan kortare än grannens avstånd hittills blir den det nya avståndet, noden sparas som vägen dit, och grannen läggs i kön om den inte redan fanns där. När kön är tom har varje nod som kan nås sitt kortaste avstånd.
Varför den närmaste noden är slutgiltig
När en nod är den närmaste i kön måste varje annan väg dit lämna den färdiga delen av grafen genom någon nod i kön, som ligger minst lika långt bort, och sedan lägga till kanter som inte kan vara negativa. Ingen annan väg kan alltså vara kortare. Det är också därför ett mål är säkert först när det tas från kön, inte när det nås första gången, och därför Dijkstras algoritm inte fungerar med negativa kanter: där behövs Bellman–Ford-algoritmen. När varje kant har längd 1 gör Dijkstras algoritm samma sak som bredden-först-sökning.
Ofta ställda frågor
Vad är Dijkstras algoritm?
Ett sätt att hitta de kortaste vägarna från en startnod till alla andra noder i en graf vars kanter har längder som är noll eller mer. Den tar gång på gång den närmaste nod som inte är klar, gör dess avstånd slutgiltigt och använder dess kanter för att korta grannarnas avstånd.
Varför fungerar inte Dijkstras algoritm med negativa kanter?
Den gör en nods avstånd slutgiltigt så snart noden är den närmaste i kön. En negativ kant som hittas senare kan fortfarande leda tillbaka till noden på en kortare väg, så det slutgiltiga avståndet kan bli fel. Bellman–Ford-algoritmen klarar negativa kanter, så länge det inte finns någon cykel med negativ summa.
Vad är skillnaden mellan Dijkstra och BFS?
Bredden-först-sökning räknar kanter och använder en vanlig kö. Dijkstras algoritm summerar kantlängder och använder en prioritetskö som alltid ger den närmaste noden. Om varje kant har längd 1 hittar båda samma avstånd.
Hur snabb är Dijkstras algoritm?
Med en binär heap som prioritetskö växer arbetet med (V + E) log V för V noder och E kanter. Med en Fibonacci-heap är det E + V log V. Appen håller kön som en sorterad lista, som är enkel att visa och räcker gott för små grafer.
Skickas min graf någonstans?
Nej. Grafen skapas och genomsöks 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