Hvad er algoritmen bag den korteste vej?
Spørg Scientariet
Nu kan du også udfordre dine venner med ekspert-spørgsmål fra Scientariet i Ingeniørens Facebook-quiz "Så ka' du lære det!".
Klik for at deltage i quizzen og test dine venner.
Læs mere om
Dokumentation
Edvard Korsbæk vil gerne kende algoritmen, der løser problemet om at finde den korteste vej:
"Da jeg læste til ingeniør for mange år siden, blev det sagt, at problemet med at finde den kortest mulige vej mellem forskellige byer ikke var løsbart, og formodentligt heller ikke ville blive det.
I dag kan jeg jo bruge en tilfældig GPS - det virker sådan set udmærket! Mit spørgsmål er: Hvordan fungerer algoritmen bagved egentligt beskrevet i forståelig prosa?"
Henning Christiansen, professor i Datalogi på Roskilde Universitet med speciale i Intelligente Systemer, svarer.
"Det er heldigvis en gal oplysning, spørgeren her har fået fat i. Problemet med korteste eller hurtigste vej kan løses effektivt og elegant med en algoritme, som blev publiceret af E.W. Dijkstra (1930–2002) i 1959.
Denne algoritme er et skoleeksempel på såkaldt dynamisk programmering: man starter med at konstruere løsninger på simplere problemer og udvider dem gradvist, til man står med en løsning til det oprindelige problem.
Princippet for algoritmen er, at man finder korteste veje fra sit startpunkt ud til alle byer i større og større omegne indtil destinationen kommer med. Vi kan forklare det springende punkt i algoritmen i forhold til figuren. 
Lad os sige, vi gerne vil til Rom, og at vi på et tidspunkt har fundet de korteste veje fra vort startpunkt ud til to byer A og B med længder 1018 og 1015, og at vi nu overvejer at finde en korteste vej til byen C. Hvis vi nu forlænger vejen til A videre til C får vi en vej med længde 1021, som ser ud til at være en god kandidat, i alt fald bedre end den via B.
Men se nu den by som er markeret med "?", hvorfor er den med på billedet, den ligger tilsyneladende i den helt gale retning. Det kan være den befinder sig et sted i Midtsverige, men at de der har en fin teleport-forbindelse til by C, og så kunne det jo være det gav anledning til en endnu kortere vej til C og i sidste ende til Rom.
Så vi finder hele tiden forslag til korteste veje, som evt. kan erstattes af bedre, og når vi så er sikre på, at en vej ud til f.eks. by A ikke kan forbedres mere, så kan vi begynde at se, om vi fra A kan foreslå gode veje ud til dens naboer, f.eks. C. Og sådan fortsætter vi til C=Rom.
Bruger vi Dijkstras algoritme efter bogen, koster det i værste fald ét check af hvert eneste vejstykke, så som A–C og B–C, på landkortet, hvilket i mange tilfælde er effektivt nok (det kan vises, at tidsforbruget er proportionalt med n x log(n), hvor n er antallet af vejstykker).
Det er interessant, at algoritmen er fremtidssikret ved at den også kan behandle teleporte. Lige nu er der ikke så mange teleporte i funktion, men vi kan genkende fænomenet, når Rejseplanen sender os i den gale retning for at springe på et lyntog.
Algoritmen kan optimeres ved at foretage analyser af landkortet i forvejen, så man får kontrol over, hvor langt man skal søge bagud og til siderne for eventuelle teleporte, lyntog eller motorveje. Man kan så at sige nøjes med at søge i et passende tykt pølseformet område ned over Europa, når man vil hurtigt til Rom, fremfor at søge ud i alle hjørner og kroge efter teknologier, som ikke er opfundet endnu.
Rejseplanen i Danmark benytter software udviklet af Hafas i Tyskland, og selvom "der Hafas-Algorithmus" er patenteret og hemmeligholdt, kan man få det indtryk, at den er en optimeret version af Dijkstras som skitseret."
Endnu en SpaceX-succes: Dragon koblet på ISS
Er mørkt stof en negativ tyngdekraft?
