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. Å finne korteste vei i en graf behøves for eksempel innenfor ruteplanlegging og i routingprotokoller.


== Algoritme ==
La 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
   være en rettet graf, med startnode 
  
    
      
        s
      
    
    {\displaystyle s}
  . (Hvis grafen er urettet, kan man erstatte hver kant med to kanter - én i hver retning). Vi antar at 
  
    
      
        s
      
    
    {\displaystyle s}
   har en vei til alle andre noder i 
  
    
      
        G
      
    
    {\displaystyle G}
  . Hver kant 
  
    
      
        e
        ∈
        E
      
    
    {\displaystyle e\in E}
   er en tuppel 
  
    
      
        e
        =
        (
        u
        ,
        v
        )
      
    
    {\displaystyle e=(u,v)}
   mellom to noder 
  
    
      
        u
      
    
    {\displaystyle u}
   og 
  
    
      
        v
      
    
    {\displaystyle v}
  . Hver kant har en lengde 
  
    
      
        
          l
          
            e
          
        
      
    
    {\displaystyle l_{e}}
   som for eksempel kan representere tid, kostnad eller avstand. Det er viktig at  
  
    
      
        
          l
          
            e
          
        
      
    
    {\displaystyle l_{e}}
   ikke kan være negativ.
Algoritmen starter med at man merker en distanse 
  
    
      
        d
        i
        s
        t
        (
        u
        )
      
    
    {\displaystyle dist(u)}
   til hver enkelt node. Avstanden til startnoden settes til null: 
  
    
      
        d
        i
        s
        t
        (
        s
        )
        =
        0
      
    
    {\displaystyle dist(s)=0}
  . For alle andre noder settes 
  
    
      
        d
        i
        s
        t
        (
        u
        )
        =
        ∞
      
    
    {\displaystyle dist(u)=\infty }
  . Man oppretter også et sett 
  
    
      
        S
      
    
    {\displaystyle S}
   som kommer til å inneholde nodene som vi har funnet den korteste veien til. I begynnelsen er 
  
    
      
        S
        =
        {
        s
        }
      
    
    {\displaystyle S=\{s\}}
  . For hver node som ikke er i 
  
    
      
        S
      
    
    {\displaystyle S}
  , finner vi den korteste veien med følgende metode:

Velg den noden 
  
    
      
        v
      
    
    {\displaystyle v}
   som det er kortest avstand til fra en node 
  
    
      
        u
      
    
    {\displaystyle u}
   i 
  
    
      
        S
      
    
    {\displaystyle S}
  . Det vil si: velg noden hvor 
  
    
      
        d
        i
        s
        
          t
          ′
        
        (
        v
        )
        =
        m
        i
        n
        (
        d
        i
        s
        t
        (
        u
        )
        +
        
          l
          
            (
            u
            ,
            v
            )
          
        
        )
      
    
    {\displaystyle dist'(v)=min(dist(u)+l_{(u,v)})}
   er minst mulig. Sett 
  
    
      
        d
        i
        s
        t
        (
        v
        )
        =
        d
        i
        s
        
          t
          ′
        
        (
        v
        )
      
    
    {\displaystyle dist(v)=dist'(v)}
  , og legg 
  
    
      
        v
      
    
    {\displaystyle v}
   til i 
  
    
      
        S
      
    
    {\displaystyle S}
  , siden vi har funnet den korteste veien til denne noden.
Fortsett med trinn 1 så lenge det er ubesøkte noder; altså så lenge 
  
    
      
        V
        −
        S
        ≠
        ∅
      
    
    {\displaystyle V-S\neq \emptyset }
  .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 
  
    
      
        S
      
    
    {\displaystyle S}
  .


== Pseudokode ==

Følgende programmering i pseudokode tar utgangspunkt i en graf 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
   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.

Eksempel: Korteste vei mellom Frankfurt og München
		
		
		
		
		
		
		
		
		
		


== Implementering ==
Dijkstras algoritme kan implementeres effektivt med en prioritetskø. Til å begynne med inneholder køen alle nodene 
  
    
      
        v
        ∈
        V
      
    
    {\displaystyle v\in V}
   utenom startnoden 
  
    
      
        s
      
    
    {\displaystyle s}
   (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 
  
    
      
        n
      
    
    {\displaystyle n}
   noder og 
  
    
      
        m
      
    
    {\displaystyle m}
   kanter ekstraherer man det minste elementet i køen maksimalt 
  
    
      
        n
      
    
    {\displaystyle n}
   ganger, og man endrer kostnaden til en node maksimalt 
  
    
      
        m
      
    
    {\displaystyle m}
   ganger. Tidskompleksiteten er derfor 
  
    
      
        O
        (
        m
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(m\log n)}
   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 ==