Dijkstras algoritm, i enkla steg
Dijkstras algoritm, utgiven av Edsger Dijkstra 1959, är en kraftfull metod för att hitta kortaste stigar mellan noder i en graf. Detta Instructable innehåller stegen av denna algoritm, att hjälpa dig med följa algoritmen på papper eller implementera det i ett program.
Notera att stegen bara spela in de kortaste väg längderna och spara inte de faktiska kortaste stigarna längs hörn. Om kunskap om sammansättningen av stigar, steg 2 och 4 kan lätt ändras för att spara dessa data i en annan associativ array: se Dijkstras 1959 papper i Numerische Mathematik för mer information.
Okej, låt oss komma igång! I dessa instruktioner antar vi har vi följande information:
- En graf G
- En uppsättning hörn V
- En uppsättning kanter E (där varje kant har en icke-negativ vikt)
- En utgångspunkt s ∈ V
Observera att den "del av"-symbolen ∈, anger att elementet på den vänstra sidan av symbolen är innesluten i samlingen på andra sidan av symbolen. S ∈ V anger exempelvis att s är en del av V - i detta fall, detta innebär att s är en brytpunkt i grafen.
Dessa riktningar är designade för användning av en publik som är bekant med grunderna i grafteori, fastställd teori och datastrukturer. Med denna förutsättning kunskap, bör alla notation och begrepp som används vara relativt enkelt för publiken.
Mer information om detaljerna för Dijkstras algoritm är Wikipedias sida om det en utmärkt resurs.