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 rediger

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)=\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^[2]:

Velg den noden $v$ som det er kortest avstand til fra en node $u$ i $S$ . Det vil si: velg noden hvor $dist'(v)=min(dist(u)+l_{(u,v)})$ er minst mulig. Sett $dist(v)=dist'(v)$ , og legg $v$ til i $S$ , siden vi har funnet den korteste veien til denne noden.
Fortsett med trinn 1 så lenge det er ubesøkte noder; altså så lenge $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 $S$ .

Pseudokode rediger

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 rediger

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 $\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 rediger

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 rediger

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

Prims Algoritme rediger

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 rediger

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 rediger

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

Referanser rediger

^ Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.
^ Kleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.

[1] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1), 269-271.

[2] Kleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.

[1]

[2]