Dijkstras algoritme

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Dijkstras algoritme er en algoritme for å finne korteste vei i en graf, først publisert av Edsger Dijkstra, og kjent fra flere anvendelser i informatikk og datakommunikasjon.

Det forutsettes en graf G=(E, V) der V er mengden noder, og E er grafens enveis (rettede) linker mellom noder. Kostnaden med å gå fra node i til j er linkkost ( i, j ), og kan ikke være negativ, samt vil være uendelig (∞) der det ikke finnes direkte link. Har man negative linkkostnader kan man bruke Bellman-Ford istedet for Dijkstra. En korteste vei i antall hopp finnes ved å sette linkkost ( i, j ) = 1 der direkte link finnes, og er kjent brukt ved ruting av informasjon i Internettet. Dijkstra er en grådig algoritme, og mye lik Prims algoritme for å finne et minimalt spenntre.

For å finne korteste vei fra utgangspunkt til alle andre noder, vil mengden UFERDIG inneholde noder som ikke er avklart. UFERDIG bør være sortert på hittil laveste sumkost, slik at det er greit å finne den noden som ligger nærmest utgangspunkt, hva kostnad angår.

  1. Initielt
    1. sumkost( i ) = ∞ (uendelig høy) og forrige ( i ) = null (ingen) for alle noder i i G
    2. sumkost( utgangspunkt ) = 0
    3. legg alle nodene i UFERDIG
  2. Sålenge det ligger noe i UFERDIG
    1. sett i til den i UFERDIG som har lavest sumkost
    2. fjern i fra UFERDIG
    3. for hver UFERDIGE node j der er rimeligere å gå til j via i
      1. sett sumkost( j ) = sumkost( i ) + linkkost( i, j )
      2. sett forrige( j ) = i
  3. Avslutningsvis
    1. rimeligste vei fra utgangspunkt til node i er sumkost( i )
    2. rimeligste vei til i avdekkes med den rekursive skrivut_vei ( i )
      1. skrivut_vei ( k ) : hvis ( k er i G) returner skrivut_vei ( forrige ( k ) ) pluss k

Kjøretiden er lineær i antall noder og kanter, men avhenger av måten man representerer linkkostnader og mengden UFERDIG (en prioritetskø er vanligst).

Eksempel fra Tyskland, utgangspunkt er Frankfurt (sumkost ( Frankfurt ) = 0.
Etter å ha vært i Frankfurt har man ny sumkost for tre av byene. Frankfurt er ikke lenger i UFERDIG.
Mannheim hadde lavest sumkost i UFERDIG, og tas derfor ut. Ny sumkost beregnet for Karlsruhe.
Etter Karlsruhe.
Etter Kassel har vi første estimat på sumkost for München, nemlig 675.
Etter Würzburg
Etter Nürnberg fant vi en rimeligere rute til München, og vi har nå også fått en sumkost for alle byene.
Etter Erfurt.
Etter Aufgsburg.
Etter München er Stuttgart den eneste i UFERDIG.
matematikkstubbDenne matematikkrelaterte artikkelen er dessverre kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den. (Se stilmanual)

Litteratur[rediger | rediger kilde]

  • E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271