Redigerer 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<ref>Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. ''Numerische mathematik'', ''1''(1), 269-271.</ref>. Å finne korteste vei i en graf behøves for eksempel innenfor ruteplanlegging og i routingprotokoller.

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

Algoritmen starter med at man merker en distanse <math>dist(u)</math> til hver enkelt node. Avstanden til startnoden settes til null: <math>dist(s)=0</math>. For alle andre noder settes <math>dist(u)=\infty</math>. Man oppretter også et sett <math>S</math> som kommer til å inneholde nodene som vi har funnet den korteste veien til. I begynnelsen er <math>S=\{s\}</math>. For hver node som ''ikke'' er i <math>S</math>, finner vi den korteste veien med følgende metode<ref>Kleinberg, J., & Tardos, E. (2006). ''Algorithm design''. Pearson Education India.</ref>:

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

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 <math>S</math>.

== Pseudokode ==
[[Fil:DijkstraDemo.gif|miniatyr|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 <math>S</math>. De blå linjene illustrerer kantene som har en ende innenfor og en ende utenfor <math>S</math>, idet algoritmen leter etter den neste noden med den minste distanskostnaden.]]
Følgende programmering i [[pseudokode]] tar utgangspunkt i en graf <math>G=(V,E)</math> 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.

<gallery widths="240" heights="240" caption="Eksempel: Korteste vei mellom Frankfurt og München">
Fil:MapGermanyGraph.svg|Den (ikke initialiserte) grafen over tyske byer.
Fil:DijkstraStep01.svg|Avstanden til startnoden Frankfurt er 0. Alle andre distansverdier settes til <math>\infty</math>. 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.
</gallery>

== Implementering ==
Dijkstras algoritme kan implementeres effektivt med en [[Kø (datastruktur)|prioritetskø]]. Til å begynne med inneholder køen alle nodene <math>v\in V</math> utenom startnoden <math>s</math> (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 <math>n</math> noder og <math>m</math> kanter ekstraherer man det minste elementet i køen maksimalt <math>n</math> ganger, og man endrer kostnaden til en node maksimalt <math>m</math> ganger. Tidskompleksiteten er derfor <math>O(m \log n)</math> 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|bredde-først søk]] (BFS).

== Referanser ==
<references />

[[Kategori:Grafalgoritmer]]