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^[1]. Å finne korteste vei i en graf behøves for eksempel innenfor ruteplanlegging og i routingprotokoller.

Algoritme

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

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

1. Velg den noden ${\displaystyle v}$ som det er kortest avstand til fra en node ${\displaystyle u}$ i ${\displaystyle S}$. Det vil si: velg noden hvor ${\displaystyle dist'(v)=min(dist(u)+l_{(u,v)})}$ er minst mulig. Sett ${\displaystyle dist(v)=dist'(v)}$, og legg ${\displaystyle v}$ til i ${\displaystyle 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 ${\displaystyle V-S\neq \emptyset }$.

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 ${\displaystyle S}$.

Pseudokode

Følgende programmering i pseudokode tar utgangspunkt i en graf ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle v\in V}$ utenom startnoden ${\displaystyle 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 ${\displaystyle n}$ noder og ${\displaystyle m}$ kanter ekstraherer man det minste elementet i køen maksimalt ${\displaystyle n}$ ganger, og man endrer kostnaden til en node maksimalt ${\displaystyle m}$ ganger. Tidskompleksiteten er derfor ${\displaystyle 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).

Referanser