Dijkstras algoritme

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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 | rediger kilde]

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 .

Pseudokode[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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

Prims Algoritme[rediger | rediger kilde]

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 | rediger kilde]

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 | rediger kilde]

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

Referanser[rediger | rediger kilde]

  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.