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.

AlgoritmeRediger

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 metode[2]:

  1. 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.
  2. 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  .

PseudokodeRediger

 
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

EksempelRediger

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.

ImplementeringRediger

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 algoritmerRediger

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

Prims AlgoritmeRediger

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-FordRediger

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økRediger

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

ReferanserRediger

  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.