Foklaring af Dijkstra's shortest path algoritme

Dijkstra’s algoritme (Korteste vej fra én knude til alle andre)
//pre: der forefindes ikke negative vægte
Placer alle knuderne i en liste og afstanden til disse som værende uendelig
Marker afstand til startknude som værende ”0” og dens forgænger som null

Sålænge der er knuder i listen
    Iterer liste med knuder igennem og udtræk den med mindste vægt som ikke har været besøgt
        Marker den udtrukne knude som besægt
        for alle naboknuder til den udtrukne knude
            opdater afstanden til disse i listen
            marker aktuel knude som værende forgænger til naboknuderne

Tidskompleksitet:
Hvis vi sekventielt leder listen igennem efter den knude med den mindste afstand tager dette O(|V|2). Dette gøres |V| gange. I tillæg sker der maksimalt en opdatering pr. kant O(|E|). Den totale tid bliver således O(|E| + |V|2) = O(|V|2).
Vælger man at bruge en prioritetskø til at holde styr på de ikke besøgte knuder kan tidskompleksiteten reduceres til O(|E| + |logV|)

Anvendelighed: reachability.

Pseudokode (retningsgraf):

knude = startknude
KA_SK = (0,null)

1  LOOP
2    hvis knude ikke i resultatsæt
3    Put knude + KA_SK i resultatsæt
4    For hver naboknude
5        SK =  (knude, naboknude)
6        KA = KA(knude) + vægt(SK)
7        Gem KA_SK i prioritetskø (prioriteret efter KA)
8    hvis prioritetskø ikke tom
9        læs og fjern KA_SK i prioritetskø (forreste element)
10        knude lig til-knude i SK
11    Ellers exit loop
12  LOOP END

Jeg har lavet en note på 10 sider omkring dijkstra, hvis du giver mig din mail, kan jeg sende den, der er også forklaring på hvordan den bruges

KA: (korteste afstand)
SK: (sidste kant)

Måske kan det bedre forklares med et eksempel:

Problem: Danmark-Finland

Knuder:

  I udgangspunktet er der uendeligt langt til alle
  lande, bortset fra Danmark, som der er 0km til.
  Ingen knuder har en pred, da denne skal indholde
  det land som den korteste sti til destinationen
  går igennem:

  Danmark{d=0km,pred=[]},
  Finland{d=oo,pred=[]},
  England{d=oo,pred=[]},
  Norge{d=oo,pred=[]}

Kanter: (Jeg er ikke så god til geografi ;-) )

  Danmark-England: 100km
  England-Finland: 250km
  Danmark-Norge: 100km
  Norge-Finland:100km

Eksekvering af dijkstra:

1: Danmark udtages (mindste d som ikke er besøgt):

  Naboer: England,Norge

  Beregninger (korteste sti til England og Norge er kantens
      længde + mindste afstand til naboen Danmark fra
      udgangspunktet (dvs 0) ):

    Danmark(0km) + Danmark-England(100km) < England(oo)
        => England.d = 0+100
      Danmark(0km) + Danmark-Norge(100km) < Norge(oo)
        => Norge.d = 0km+100km

  Resultat:
      Danmark{d=100km,pred=[]},
      Finland{d=oo,pred=[]},
      England{d=100km,pred=[Danmark]},
      Norge{d=100km,pred=[Danmark]}

2: England udtages (mindste d som ikke er besøgt):

  Naboer: Finland

  Beregninger:
      England(100km) + England-Finland(250km) < Finland(oo)
        => Finland.d = 100km+250km og Finland.pred=England

  Resultat:
      Danmark{d=0km,pred=[]},
      Finland{d=350km,pred=[England]},
      England{d=100km,pred=[Danmark]},
      Norge{d=100km,pred=[Danmark]}

3: Norge udtages (mindste d som ikke er besøgt):

  Naboer: Finland

  Beregninger:

      Norge(100km) + Norge-Finland(100km) < Finland(350km)
        => Finland.d = 100km + 100km

  Resultat:
      Danmark{d=0km,pred=[]},
      Finland{d=200km,pred=[Norge]},
      England{d=100km,pred=[Danmark]},
      Norge{d=100km,pred=[Danmark]}

4: Finland udtages (mindste d som ikke er besøgt):

  - ingen naboer


Færdig:
  Korteste sti til Finland fra Danmark:
      200km gennem Norge (Norge pred til Danmark, Danmark pred til Norge)

  Korteste sti til England fra Danmark: 100km direkte
  etc

Der skulle have stået:

Færdig:
  Korteste sti til Finland fra Danmark:
      200km gennem Norge (Norge pred til _Finland_, Danmark pred til Norge)

Hej...Tak for svar...Jeg har lige haft et par travle dage og har derfor ikke fået kigget på det, men jeg sætter mig til tasterne nu i aften og forsøger at implementere..

Mvh Casualty

janl2000 >> Min mail er anders@bluepage.dk du må meget gerne sende mig din note

Hej igen, jeg har sendt en note om Dijkstra til dig + et lille kode eksempel, der viser hvordan teorien kan bruges. Håber det kan bruges

Tak for hjælpen :)

Er det muligt at få en kopi af den meget omtalte note?