Dijkstras algoritme

Dijkstras algoritme er en grådig algoritme for å finne korteste vei fra en gitt node til alle andre noder i en graf. Den ble publisert av Edsger Dijkstra i 1959. Å finne korteste vei i en graf behøves for eksempel innenfor ruteplanlegging og i routingprotokoller.

Algoritme

La $G=(V,E)$ være en rettet graf, med startnode $s$. (Hvis grafen er urettet, kan man erstatte hver kant med to kanter - én i hver retning). Vi antar at $s$ har en vei til alle andre noder i $G$. Hver kant $e\in E$ er en tuppel $e=(u,v)$ mellom to noder $u$ og $v$. Hver kant har en lengde $l_e$ som for eksempel kan representere tid, kostnad eller avstand. Det er viktig at $l_e$ ikke kan være negativ.

Algoritmen starter med at man merker en distanse $dist(u)$ til hver enkelt node. Avstanden til startnoden settes til null: $dist(s)=0$. For alle andre noder settes $dist(u)=\mathrm{\infty }$. Man oppretter også et sett $S$ som kommer til å inneholde nodene som vi har funnet den korteste veien til. I begynnelsen er $S=\{s\}$. For hver node som ikke er i $S$, finner vi den korteste veien med følgende metode:

1. Velg den noden $v$ som det er kortest avstand til fra en node $u$ i $S$. Det vil si: velg noden hvor $dis{t}^{\prime }(v)=min(dist(u)+l_{(u,v)})$ er minst mulig. Sett $dist(v)=dis{t}^{\prime }(v)$, og legg $v$ til i $S$, siden vi har funnet den korteste veien til denne noden.
2. Fortsett med trinn 1 så lenge det er ubesøkte noder; altså så lenge $V-S\ne \mathrm{\varnothing }$.

Dijkstras algoritme kan også finne korteste vei fra en startnode til en bestemt sluttnode. Da endrer man trinn 2 og terminerer så snart den ønskede sluttnoden har blitt lagt til i $S$.

Pseudokode

En demonstrasjon av Dijkstras algoritme, basert på avstand i rommet. De røde linjene er de korteste veiene, det vil si kanter mellom nodene i $S$. De blå linjene illustrerer kantene som har en ende innenfor og en ende utenfor $S$, idet algoritmen leter etter den neste noden med den minste distanskostnaden.

Følgende programmering i pseudokode tar utgangspunkt i en graf $G=(V,E)$ og en startnode, og beregner korteste vei til alle andre noder i grafen. Hver kant i grafen har en kostnad.

 1  Dijkstra(Graf G, Startnode s):
 2     For hver node u i G
 3          sett dist(u) til uendelig
 4     dist(s) ← 0
 5     S ← {s}        
 7     Så lenge S ≠ V
 8          blant alle v i settet V-S som har en kant til en node u i S
 9              velg noden v som minimerer dist(u) + kantkostnad
 10         dist(v) ← dist(u) + kantkostnad
 11         legg til v i S
 12    returner S

Eksempel

Følgende eksempel viser hvordan algoritmen finner den korteste veien mellom to byer. Startpunktet er Frankfurt, og målet er München. Hver by er en node i grafen. Kantkostnadene er avstandene mellom to byer.

• Eksempel: Korteste vei mellom Frankfurt og München
• 
  Den (ikke initialiserte) grafen over tyske byer.
• 
  Avstanden til startnoden Frankfurt er 0. Alle andre distansverdier settes til $\mathrm{\infty }$. Avstandene til naboene til Frankfurt oppdateres.
• 
  På dette tidspunktet er det kortest avstand til Mannheim. Derfor blir denne noden valgt, og avstanden til Karlsruhe blir oppdatert.
• 
  Det er kortere avstand til Karlsruhe enn til både Würzburg og Kassel. Derfor velges Karlsruhe, og avstanden til Augsburg blir oppdatert.
• 
  Nå er det Kassel det er kortest vei til. Avstanden til München blir oppdatert.
• 
  Noden "München" kan ikke bli valgt helt enda, fordi det er kortere vei til Würzburg. Avstanden til de nodene man kan nå ved å reise gjennom Würzburg, blir oppdatert.
• 
  Avstanden til Nürnberg er nå den korteste av alle avstander til de uferdige nodene. Oppdater avstanden til München.
• 
  Erfurt er neste ut. Noden har ingen naboer. Ingen andre noder oppdateres.
• 
  Av de uferdige nodene er det nå kortest avstand til Augsburg. Noden München oppdateres ikke, fordi den nåværende veien gjennom Nürnberg er kortere.
• 
  Endelig har München kortest avstand blant de uferdige nodene. Det er ikke nødvendig å betrakte noden Stuttgart. Problemet er løst; den korteste avstanden fra Frankfurt til München er 487.

Implementering

Dijkstras algoritme kan implementeres effektivt med en prioritetskø. Til å begynne med inneholder køen alle nodene $v\in V$ utenom startnoden $s$ (som man allerede kjenner avstanden til). I hvert trinn tar man ut noden det er kortest avstand til; eventuelt må man oppdatere avstanden til denne nodens naboer. For en graf med $n$ noder og $m$ kanter ekstraherer man det minste elementet i køen maksimalt $n$ ganger, og man endrer kostnaden til en node maksimalt $m$ ganger. Tidskompleksiteten er derfor $O(m\log n)$ når man bruker en heap-basert prioritetskø.

Beslektede algoritmer

Søkealgoritmen A* bruker en ekstensjon av Dijkstras algoritme. Andre eksempler på relaterte algoritmer er:

Prims Algoritme

Prims algoritme, som finner et minimalt spenntre, ligner Dijkstras algoritme. Forskjellen ligger i at man, i hvert skritt, utforsker den neste kanten som isolert sett har den minste kostnaden.

Bellman-Ford

Kantkostnadene i Dijkstras algoritme kan ikke være negative. Hvis man vil finne korteste vei i en graf med negative kanter, kan man bruke Bellman-Ford-algoritmen, som er basert på dynamisk programmering.

Bredde-Først-Søk

Hvis grafen er uvektet, eller hvis alle kantetene har samme kostnad, så er Dijkstras analogt med bredde-først søk (BFS).