Dijkstras algoritme
Din ruteplanlægger kender den hurtigste vej fra din dør til næsten hvor som helst. Kernen i den idé er en algoritme, som Edsger Dijkstra udtænkte på omkring tyve minutter i 1956: voks udad fra starten, og gør altid det nærmeste sted færdigt først.
Idéen
Forestil dig byer forbundet af veje med forskellige længder. Spørgsmålet er: hvad er den korteste vej fra min by til hver af de andre? Bredde-først-søgning svarer på det, når hver vej tæller det samme, men her kan en rute med flere veje være kortere. Dijkstras algoritme holder for hver by styr på den korteste afstand, der er fundet indtil nu, og lader et område af byer, hvis afstand er sikker, vokse ved altid at tilføje den nærmeste by, der ikke er sikker endnu.
Trin for trin
Giv starten afstand 0 og alle andre knuder uendelig. Sæt starten i en prioritetskø, en kø, der altid giver knuden med den mindste afstand. Tag den knude; dens afstand er nu endelig. For hver nabo, der ikke er endelig, beregn afstanden gennem denne knude: knudens afstand plus kantens længde. Er det kortere end naboens afstand indtil nu, så sænk den, husk denne knude som vejen dertil, og sæt naboen i køen. Det kaldes at relaksere en kant. Gentag, indtil køen er tom, eller indtil målet tages fra den.
Et eksempel
Tag kanterne A–B med længde 4, A–C 1, B–C 2, B–D 1, C–D 5 og D–E 3, og start i A. At tage A giver B afstand 4 og C afstand 1. C er nærmest, så den er endelig med 1; gennem C falder B til 1 + 2 = 3, og D får 1 + 5 = 6. Nu er B nærmest, endelig med 3, og gennem B falder D til 3 + 1 = 4. D er endelig med 4 og giver E 4 + 3 = 7. Så den korteste vej fra A til E er A → C → B → D → E med længde 7, selvom A → B → D → E bruger færre kanter og har længde 8.
Hvorfor den er korrekt
Antag, at knude X er den nærmeste i køen med afstand d. Enhver anden vej fra starten til X må forlade området af endelige knuder på et tidspunkt, og den første knude, den når uden for området, er i køen, så den er allerede mindst d væk. Resten af vejen kan ikke gøre den kortere, for ingen kant er negativ. Så d er den korteste afstand til X. Med en negativ kant holder argumentet ikke; så bruger man i stedet Bellman–Ford-algoritmen, som relakserer hver kant igen og igen.
Historie og anvendelser
Edsger W. Dijkstra udtænkte algoritmen i 1956 for at vise en ny computer frem, ARMAC i Amsterdam, ved at finde ruter mellem hollandske byer, og offentliggjorde den i 1959. Den samme idé, med en smartere kø, kører i ruteplanlæggere og i internettets routingprotokoller som OSPF og IS-IS, der finder den korteste vej for data mellem routere. A*-søgning tilføjer et gæt på den afstand, der er tilbage, så den kan styre mod målet og se på færre knuder.
Prøv selv
Åbn appen, og tryk på Trin. Tallene på kanterne er deres længder, og tallet på hver knude er dens afstand indtil nu. Knuder i køen er blå, endelige knuder grønne, og køen under grafen viser dem med deres afstande, nærmeste først. Læg mærke til de øjeblikke, hvor en afstand falder, fordi en rute, der ser længere ud, viser sig at være kortere, og vælg et mål for at se søgningen stoppe, så snart målet er endeligt.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for Dijkstras algoritme?
Det afhænger af prioritetskøen. Med en simpel liste er den O(V²) for V knuder; med en binær hob O((V + E) log V) for E kanter; med en Fibonacci-hob O(E + V log V), som Michael Fredman og Robert Tarjan viste i 1984.
Kan Dijkstras algoritme håndtere negative kantvægte?
Nej. Den går ud fra, at en knudes afstand ikke kan forbedres, når knuden er den nærmeste i køen, og det kan en negativ kant ødelægge. Brug Bellman–Ford-algoritmen til grafer med negative kanter.
Finder Dijkstras algoritme vejen til hver knude?
Ja. Kørt til ende giver den den korteste afstand fra starten til hver knude, der kan nås, og de huskede knuder danner et træ af korteste veje. At stoppe tidligt, når målet er endeligt, sparer arbejde, når du kun skal bruge én vej.
Hvordan hænger Dijkstras algoritme sammen med A*?
A*-søgning er Dijkstras algoritme med et fingerpeg: den ordner køen efter afstanden indtil nu plus et skøn over den afstand, der er tilbage, for eksempel afstanden i luftlinje på et kort. Med et godt skøn finder den den samme korteste vej og ser på langt færre knuder.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv Dijkstras algoritme