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

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

Algoritmen starter med at man merker en distanse  til hver enkelt node. Avstanden til startnoden settes til null: . For alle andre noder settes . Man oppretter også et sett  som kommer til å inneholde nodene som vi har funnet den korteste veien til. I begynnelsen er . For hver node som ikke er i , finner vi den korteste veien med følgende metodeKleinberg, J., & Tardos, E. (2006). Algorithm design. Pearson Education India.:

 Velg den noden  som det er kortest avstand til fra en node  i . Det vil si: velg noden hvor  er minst mulig. Sett , og legg  til i , siden vi har funnet den korteste veien til denne noden.
 Fortsett med trinn 1 så lenge det er ubesøkte noder; altså så lenge .

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 .

 Pseudokode 
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 . De blå linjene illustrerer kantene som har en ende innenfor og en ende utenfor , idet algoritmen leter etter den neste noden med den minste distanskostnaden.
Følgende programmering i pseudokode tar utgangspunkt i en graf  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.

 Implementering 
Dijkstras algoritme kan implementeres effektivt med en prioritetskø. Til å begynne med inneholder køen alle nodene  utenom startnoden  (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  noder og  kanter ekstraherer man det minste elementet i køen maksimalt  ganger, og man endrer kostnaden til en node maksimalt  ganger. Tidskompleksiteten er derfor  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 

Kategori:Grafalgoritmer