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)=\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:

# 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

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.


Fil:MapGermanyGraph.svg|Den (ikke initialiserte) grafen over tyske byer.
Fil:DijkstraStep01.svg|Avstanden til startnoden Frankfurt er 0. Alle andre distansverdier settes til \infty. Avstandene til naboene til Frankfurt oppdateres.
Fil:DijkstraStep02.svg|På dette tidspunktet er det kortest avstand til Mannheim. Derfor blir denne noden valgt, og avstanden til Karlsruhe blir oppdatert.
Fil:DijkstraStep03.svg|Det er kortere avstand til Karlsruhe enn til både Würzburg og Kassel. Derfor velges Karlsruhe, og avstanden til Augsburg blir oppdatert.
Fil:DijkstraStep04.svg|Nå er det Kassel det er kortest vei til. Avstanden til München blir oppdatert.
Fil:DijkstraStep05.svg|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.
Fil:DijkstraStep06.svg|Avstanden til Nürnberg er nå den korteste av alle avstander til de uferdige nodene. Oppdater avstanden til München.
Fil:DijkstraStep07.svg|Erfurt er neste ut. Noden har ingen naboer. Ingen andre noder oppdateres.
Fil:DijkstraStep08.svg|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.
Fil:DijkstraStep09.svg|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).

## Referanser