Tässä blogikirjoituksessa selitämme Dijkstran algoritmin periaatteet, esimerkit ja käytännön sovellukset helposti ymmärrettävällä tavalla.
esittely
Mietipä satua ”Hannu ja Kerttu”. Kun heidän äitipuolensa hylkäsi lapset metsään, heidän ensimmäinen yrityksensä – pudottaa kiviä polun merkitsemiseksi – epäonnistui, eikä heidän toinen yrityksensä – jättää leivänmuruja – päättynyt epäonnistumiseen, koska linnut söivät heidät. Jos älypuhelinten navigointi- tai karttasovelluksia olisi ollut olemassa silloin, sisarukset eivät olisi eksyneet ja heidän äitipuolensa suunnitelma olisi kariutunut. Kuten tämä esimerkki osoittaa, ongelma ”löytää nopein reitti lähtöpisteestä määränpäähän” on pysynyt keskeisenä aiheena läpi historian, muinaisista tarinoista nykypäivän teknologiaan.
Graafit ja peruskäsitteet
Ymmärtääksemme Dijkstran algoritmin meidän on ensin määriteltävä, mitä "graafi" tarkoittaa tietojenkäsittelytieteen kontekstissa. Tässä graafi ei ole tasolle piirretty funktionaaligraafi, vaan pikemminkin tietorakenne, joka koostuu joukosta solmuja ja niitä yhdistävistä kaarista. Jos esimerkiksi ajattelemme solmuja metroasemina tai bussipysäkkeinä, kaarista tulee näitä solmuja yhdistäviä rautateitä tai teitä.
Reunoille voidaan antaa painoja; nämä arvot edustavat mitattavia kustannuksia, kuten kahden kärjen välisen matkan kestoa tai aikaa. Lisäksi, jos reunoilla on suunnat, graafista tulee "suunnattu graafi", jossa liike on sallittu vain nuolen suuntaan. Dijkstran algoritmi laskee lyhimmän etäisyyden ja polun tietystä lähtöpisteestä jokaiseen muuhun tällaisen graafin kärkeen.
Miten Dijkstran algoritmi toimii
Selitetään algoritmi yleisen esimerkin avulla. Lähtöpisteen alkuarvoksi asetetaan 0, kun taas kaikkien muiden pisteiden alkuarvoiksi asetetaan äärettömyys (∞), mikä tarkoittaa, että yhteystietoja ei vielä ole. Nämä arvot edustavat "lyhintä tunnettua matkaa (tai aikaa) tähän mennessä kyseisen pisteen saavuttamiseksi lähtöpisteestä".
Ensimmäisessä vaiheessa (vaihe 1) aloitamme asettamalla lähtösolmun arvoksi 0. Toisessa vaiheessa (vaihe 2) kaikille lähtösolmusta suoraan saavutettavissa oleville naapurisolmuille tallennetaan väliaikainen arvo lisäämällä lähtösolmun arvo (0) vastaavan kaaren painoon. Esimerkissä nämä arvot tallennetaan arvoina 8, 9 ja 11. Tässä vaiheessa lähtösolmun käsittely on valmis.
”Käsitellyllä kärkipisteellä” tarkoitetaan kärkipistettä, jolle ei löydy lyhyempää polkua, eli sen lopullinen lyhin etäisyys on määritetty. Dijkstran algoritmissa, kun lyhin etäisyys kärkipisteeseen on määritetty tällä tavalla, kyseinen kärkipiste merkitään käsitellyksi, eikä sen arvoa enää koskaan muuteta.
Kolmannessa vaiheessa (vaihe 3) valitsemme tähän mennessä tallennetuista väliaikaisista arvoista pienimmän arvon omaavan kärkipisteen. Esimerkissä valitaan kärkipiste, jonka arvo on 8. Tästä kärkipisteestä alkaen etäisyyksiä lähtöpisteestä tähän kärkipisteeseen käytetään ympäröivien kärkipisteiden arvojen päivittämiseen. Tämän prosessin aikana tapahtuu päivityksiä – esimerkiksi joidenkin vierekkäisten kärkipisteiden uusiksi ehdokasetäisyyksiksi lasketaan 18. Kun tämän kärkipisteen käsittely on valmis, se merkitään myös käsitellyksi.
Neljännessä vaiheessa (vaihe 4) käsittelemme seuraavaksi pienimmän arvon omaavan kärkipisteen – tässä esimerkissä sen, jonka arvo on 9. Myös tälle kärkipisteelle laskemme sen viereisten kärkipisteiden ehdokasetäisyydet samalla tavalla. Tämän prosessin aikana kärkipisteille, joille on jo määritetty arvot, voi ilmestyä uusia ehdokasarvoja (esim. 15, 10, 12). Jos uusi arvo on pienempi kuin olemassa oleva arvo, se korvaa olemassa olevan arvon; muuten alkuperäinen arvo säilyy. Tätä operaatiota kutsutaan "reunan relaksoinniksi", ja se on välttämätön toimenpide, koska etsimme aina lyhintä polkua.
Viidennestä vaiheesta (vaihe 5) alkaen sama menetelmä toistetaan. Joka kerta valitaan käsittelemättömien joukosta se solmu, jolla on pienin väliaikainen arvo, ja sen viereisten solmujen väliaikaiset arvot päivitetään relaksoimalla niitä viereisten kaarten kautta. Toistamalla tätä prosessia, kunnes kaikki solmut on käsitelty, voimme määrittää lyhyimmät etäisyydet lähtöpisteestä jokaiseen solmuun sekä lyhyimmät polut.
Sovellusesimerkki: Verkot ja reitittimet
Tietokoneverkot ovat erinomainen esimerkki alasta, jolla Dijkstran algoritmia käytetään laajalti käytännössä. Koska miljardien laitteiden suora kytkeminen yhteen verkkoon – kuten internetin tapauksessa – olisi tehotonta, lähekkäin olevat laitteet muodostavat paikallisia verkkoja, jotka sitten kytketään korkeamman tason verkkoihin hierarkkisessa rakenteessa. Tällaisessa monimutkaisessa yhteysrakenteessa on lukemattomia polkuja laitteesta toiseen.
Verkossa jokaisen solmun (kuten reitittimen) on arvioitava polkuja tiettyjen kustannusten (kaistanleveys, latenssi jne.) perusteella ja löydettävä "nopein" tai "halvin" polku määränpäähän. Reitittimet käyttävät lyhimmän reitin algoritmeja, kuten Dijkstran algoritmia, määrittääkseen optimaalisen reitin – eli seuraavan hypyn – johon niiden tulisi välittää liikenne. Koska reaaliaikaiset liikenneolosuhteet muuttuvat kuitenkin jatkuvasti, on käytännöllisempää, että jokainen reititin antaa tietoa vain välittömästi seuraavasta verkkosegmentistä – sen sijaan, että reititin ilmoittaisi kiinteän, täydellisen polun – ja että jokainen reititin päivittää näitä tietoja lennossa polun rakennettaessa.
Johtopäätös: Polun etsinnän opetukset
Tähän mennessä olemme tarkastelleet Dijkstran algoritmin peruskäsitteitä, sen vaiheittaista toimintaa ja sitä, miten sitä sovelletaan verkoissa. Jos Hannu ja Kerttu olisivat halunneet välttää eksymisen metsään, he olisivat tarvinneet luotettavamman navigointimenetelmän kuin yksinkertaiset merkit. Itse asiassa Dijkstran algoritmin kaltaiset algoritmit toimivat samalla tavalla navigoidessamme tai dataa siirrettäessä. Toivon, että pidät Dijkstran algoritmin taustalla olevat ideat mielessäsi, jotta et hämmentyisi kulkiessasi tuntematonta polkua ja löydät tehokkaita reittejä jopa monimutkaisissa verkoissa.
