Dijkstras algoritm
From Wikipedia, the free encyclopedia
Dijkstras algoritm är en matematisk algoritm för att hitta den kortaste eller billigaste vägen från en given nod till alla andra noder i en viktad graf med positiva bågkostnader. Grafen kan vara riktad eller oriktad. Algoritmen har fått sitt namn efter Edsger Dijkstra, som utvecklade den år 1959. Den är en algoritm som systematiskt löser Bellmans ekvationer. Dijkstras algoritm är lite av ett specialfall när det kommer till algoritmer. I inledande steg är den att liknas vid en girig algoritm som alltid väljer den kortaste vägen mellan två noder. Den avslutas emellertid med att söka igenom hela den genomgångna grafen efter den totalt sett kortaste vägen, vilket gör algoritmen till ett mellanting mellan en girig algoritm och en algoritm som använder sig av dynamisk programmering.
Uppkallad efter | Edsger Dijkstra | |
---|---|---|
Förlaga | Bredd-först-sökning | |
Upptäckare eller uppfinnare | Edsger Dijkstra | |
Upptäcktsdatum | 1959 | |
Löser | shortest path problem, pathfinding, single-source shortest path problem | |
Tidskomplexitet i värsta fall | , |
Lösningar till problemet med den billigaste vägen behövs inom många områden, exempelvis inom ruttplanering för att hitta den kortaste vägen när transportsträckor läggs ut. Den används också inom webbaserade reseplanerare för kollektivtrafik för att hitta snabbaste vägen.[1]