I dette blogindlæg vil vi forklare principperne, eksemplerne og den praktiske anvendelse af Dijkstras algoritme på en letforståelig måde.
Introduktion
Tænk tilbage på eventyret "Hans og Grete". Da deres stedmor forlod børnene i skoven, mislykkedes deres første forsøg – at smide småsten for at markere deres vej – og deres andet forsøg – at efterlade brødkrummer – endte ikke med en fiasko, fordi fuglene spiste dem. Hvis der havde eksisteret smartphone-navigations- eller kortlægningsapps dengang, ville søskende ikke være faret vild, og deres stedmors plan ville være faldet fra hinanden. Som dette eksempel viser, har problemet med at "finde den hurtigste rute fra et udgangspunkt til en destination" været et afgørende emne gennem historien, fra gamle fortællinger til nutidens teknologi.
Grafer og grundlæggende begreber
For at forstå Dijkstras algoritme, skal vi først definere, hvad en "graf" betyder i datalogiens kontekst. Her er en graf ikke en funktionel graf tegnet på et plan, men snarere en datastruktur bestående af et sæt hjørner og de kanter, der forbinder dem. Hvis vi for eksempel tænker på hjørner som metrostationer eller busstoppesteder, bliver kanterne til jernbanelinjer eller veje, der forbinder disse hjørner.
Kanter kan have tildelt vægte; disse værdier repræsenterer målbare omkostninger, såsom den afstand eller tid, der kræves for at bevæge sig mellem to hjørner. Derudover, hvis kanter har retninger, bliver grafen en "rettet graf", hvor bevægelse kun er tilladt i pilens retning. Dijkstras algoritme beregner den korteste afstand og sti fra et specifikt startpunkt til alle andre hjørner i en sådan graf.
Hvordan Dijkstra-algoritmen fungerer
Lad os forklare algoritmen ved hjælp af et almindeligt eksempel. Startværdien for startpunktet er sat til 0, mens startværdierne for alle andre hjørner er sat til uendelig (∞), hvilket betyder, at der endnu ikke er nogen forbindelsesinformation. Disse værdier repræsenterer "den korteste kendte afstand (eller tid) indtil videre for at nå det pågældende hjørne fra startpunktet."
I det første trin (trin 1) starter vi med startpunktet sat til 0. I det andet trin (trin 2) registrerer vi for alle tilstødende hjørner, der er direkte tilgængelige fra startpunktet, en midlertidig værdi for hver af dem ved at lægge startpunktets værdi (0) til vægten af den tilsvarende kant. I eksemplet registreres disse værdier som 8, 9 og 11. På dette tidspunkt er behandlingen af startpunktet færdig.
Et "behandlet hjørne" refererer til et hjørne, for hvilket der ikke kan findes en kortere vej, hvilket betyder, at dets endelige korteste afstand er blevet bestemt. I Dijkstras algoritme markeres hjørnet som behandlet, når den korteste afstand til et hjørne er bestemt på denne måde, og dets værdi ændres aldrig igen.
I det tredje trin (trin 3) vælger vi det hjørne med den mindste værdi blandt de midlertidige værdier, der er registreret indtil videre. I eksemplet vælges hjørnet med en værdi på 8. Med udgangspunkt i dette hjørne bruges afstandene fra startpunktet til dette hjørne til at opdatere værdierne for de omkringliggende hjørner. Gennem denne proces sker der opdateringer – for eksempel beregnes de nye kandidatafstande for nogle tilstødende hjørner som 18. Når behandlingen af dette hjørne er færdig, markeres det også som behandlet.
I det fjerde trin (trin 4) behandler vi hjørnet med den næstmindste værdi – i dette eksempel det med en værdi på 9. For dette hjørne beregner vi også kandidatafstande for dets tilstødende hjørner på samme måde. Under denne proces kan nye kandidatværdier (f.eks. 15, 10, 12) vises for hjørner, der allerede har tildelte værdier. Hvis en ny værdi er mindre end den eksisterende, overskriver den den eksisterende værdi; ellers bevares den oprindelige værdi. Denne operation kaldes "kantrelaksation", og det er en nødvendig procedure, fordi vi altid søger den korteste vej.
Fra det femte trin (trin 5) gentages den samme metode. Hver gang vælges det hjørne med den mindste midlertidige værdi blandt dem, der endnu ikke er behandlet, og de midlertidige værdier for dets tilstødende hjørner opdateres ved at afspænde dem gennem de tilstødende kanter. Ved at gentage denne proces, indtil alle hjørner er blevet behandlet, kan vi bestemme de korteste afstande fra startpunktet til hvert hjørne, såvel som de korteste stier.
Applikationseksempel: Netværk og routere
Computernetværk er et godt eksempel på et felt, hvor Dijkstras algoritme er meget anvendt i praksis. Da det ville være ineffektivt for milliarder af enheder at være direkte forbundet til et enkelt netværk – som det er tilfældet med internettet – danner enheder i umiddelbar nærhed lokale netværk, som derefter er forbundet til netværk på højere niveau i en hierarkisk struktur. I en så kompleks forbindelsesstruktur er der utallige stier fra én enhed til en anden.
I et netværk skal hver node (såsom en router) evaluere stier baseret på bestemte omkostninger (båndbredde, latenstid osv.) og finde den "hurtigste" eller "billigste" sti til destinationen. Routere bruger algoritmer til kortest sti, såsom Dijkstras algoritme, til at bestemme den optimale sti - det vil sige det næste hop - som de skal videresende trafik til. Men da trafikforholdene i realtid konstant ændrer sig, er det mere praktisk for hver router kun at give information om det umiddelbart næste netværkssegment - snarere end at en router annoncerer en fast, komplet sti - og at hver router opdaterer disse oplysninger løbende, efterhånden som stien konstrueres.
Konklusion: Lektioner fra Pathfinding
Indtil videre har vi undersøgt de grundlæggende koncepter i Dijkstras algoritme, dens trinvise betjening, og hvordan den anvendes i netværk. Hvis Hans og Grete havde ønsket at undgå at fare vild i skoven, ville de have haft brug for en mere pålidelig navigationsmetode end simple markører. Faktisk spiller algoritmer som Dijkstras en lignende rolle, når vi navigerer eller overfører data. Jeg håber, at du vil huske på ideerne bag Dijkstras algoritme, så du ikke bliver forvirret, når du rejser ad en ukendt sti, og kan finde effektive ruter selv inden for komplekse netværk.
