Dijkstras ”korteste vei”-algoritme

[Ulopolitanus]

Jeg blir snart gal!

 

Noen som skjønner seg veldig godt på Dijkstras ”korteste vei”-algoritmen?

 

Har en oppgave som jeg har sittet med i hele dag nå, men får det bare ikke til. Har prøvd å lete opp hjelpemidler på nett, men har enda ikke lykkes med det.

 

Kan noen forklare meg dette:

 

Anta et nett som vist i figuren nedenfor. Bruk Dijkstras ”korteste vei”-algoritme for å beregne korteste vei fra F til alle andre noder med grunnlag i de oppgitte linkkostnadene. Vis hvordan algoritmen arbeider ved å lage en tabell slik som vist i læreboka og under forelesningene.

[ve_gard]

http://no.wikipedia.org/wiki/Dijkstras_algoritme

 

Håper denne hjelper deg:)

 

mvh Vegard

[Ulopolitanus]

Har sett faktisk på den også, uten at det hjalp. Må vel studere den enda mer. Huff!

[Xvani]

korteste vei er den veien det koster minst å gå.

ved første øyekast fra F-A:

 

F-E, E-D, D-C, C-A

total cost:

1+1+1+2+1

[Iyon]

Jeg fant en java applet forrige gang jeg satt meg inn i den algoritmen, den viste stegvis hva den gjorde, husker at den var ganske informativ, skal forsøke å finne den igjen...

[Ulopolitanus]

Xvani: Så enkelt? jhsveli: Høres supert ut. Takker på forhånd.

[Torsph]

Den er ikke så veldig vanskelig, er bare å finne den korteste veien

 

Xvani sin er vel ikke helt rett??

 

For å finne korteste vei fra utgangspunkt til alle andre noder, vil mengden UFERDIG inneholde noder som ikke er avklart.

 

Den sier vel at du skal finne korteste vei til alle nodene.. Mens du har vel bare funne til FEDCA ?

 

 

Her er forresten en java applet som viser hele greia

 

LINK

Endret 3. mai 2007 av NeXz

[the_bjarne]

Dijkstras finner korteste vei fra EN startnode, til alle andre noder i grafen(en-til-alle). I en vektet graf vil det si å finne den den vegen med minst kostnad fra en startnode til alle andre noder i graden.

 

Du starter med å sette konstaden for alle nodene til uendelig, bortsett fra startnoden som du gir kostnad 0.

 

Så velger du den noden med minst kostnad( i dette tilfellet startnoden), og oppdaterer kostnadene for alle dens nabonoder. Det vil si at du gir hver nabonode den laveste verdien av disse to;

- Verdien av den valgte noden + kostnadene av kanten til noden.

- Den kostanden den allerde er registert med.

Dersom du velger den øverste av disse to, må du også lagre i noden hvilken noden den kanten kommer fra.

Når du har gjort dette for alle nabonodene, merker du startnoden som "fullført".

 

Velg igjen den noden med lavest verdi(som ikke er merket som "fullført"), og oppdater kostandene,(noden som kanten kom fram om nødvendig), marker som "fullført", og fortsett til alle nodene er markert som "fullført".

 

Nå har du kjørt algoritmen ferdig.

 

Hver node vil nå ha en kostnad, og en bokstav. Du kan finne den korteste veien fra start til hvilken som helst node, ved å begynne i den siste noden, gå til den bokstaven som står der og fortsette slik til du kommer til startnoden.

-------

I oppgaven du hadde, vil det da bli slik(med F som startnode):

setter alle kostander tiil uendelig, bortsett fra F som får kostanad 0.

 

Velger noden med minst kostnad, F, og oppdaterer dens naboer:

G:5(fraF) - D:3(fraF) - E:1(fraF)

markerer F som fullført, og velger den naboen med minst kostnad: E

 

Gjennta til alle er markert fullført

 

 

Endret 3. mai 2007 av the_bjarne

[Ulopolitanus]

Høres greit ut.

 

Hva blir da svaret på oppgaven ovenfor?

 

Og hvordan skal jeg forklare følgende: "Vis/forklar hvordan tabellen du laget ovenfor brukes til å finne ruten med lavest kostnad fra F til A."

[the_bjarne]

Høres greit ut.

 

Hva blir da svaret på oppgaven ovenfor?

 

 

Hmm... Finner ikke ut av tabeller på denne siden, men kan ta di første stegene:

 

Setter alle kostander til uendelig, bortsett fra startnoden, som settes til 0.

 

Node Kostnad Fra Fullført

G - - nei

F 0 - nei

E - - nei

D - - nei

C - - nei

B - - nei

A - - nei

 

Velger så den noden med minst kostnad, her F, og oppdaterer dens naboer, som jeg ser fra grafen at er G, D og E, og markerer F som fullført.

 

Node Kostnad Fra Fullført

G 5 F nei

F 0 - ja

E 1 F nei

D 3 F nei

C - - nei

B - - nei

A - - nei

 

Velger igjen den noden med minst kostnad(som ikke er fullført), her E, og oppdaterer dens naboer, som jeg ser fra grafen at er D og C ( F er fullført, så den tar jeg ikke med), og markerer E som fullført.

Ser at D får mindre verdi dersom jeg velger E sin kostnad + kanten fra E til D, og oppdaterer dermed dens kostand til 2, og dens fra node til E

 

Node Kostnad Fra Fullført

G 5 F nei

F 0 - ja

E 1 F ja

D 2 E nei

C - - nei

B - - nei

A - - nei

 

Velger igjen den noden med minst kostnad(som ikke er fullført), her D, og oppdaterer dens naboer, som jeg ser fra grafen at er G og C(E er fullført, så den tar jeg ikke med), og markerer D som fullført.

Ser at C kan få verdien 3, og at G kan få verdien 3, og oppdater også deres fra-noder til D

 

Node Kostnad Fra Fullført

G 3 D nei

F 0 - ja

E 1 F ja

D 2 E ja

C 3 D nei

B - - nei

A - - nei

 

Sånn, resten får du gjøre selv... slik at du lærer noe

 

Et lite tips : Dersom det er to noder som begge har lavest kostnad, har det ingenting å si hvilken du velger.

 

 

 

Og hvordan skal jeg forklare følgende: "Vis/forklar hvordan tabellen du laget ovenfor brukes til å finne ruten med lavest kostnad fra F til A."

8534627[/snapback]

 

Når alle nodene har blitt markert som fullført er du ferdig med algoritmen.

Da kan du gå inn i den siste tabellen din, for node A og se hvilken fra-node den står oppført med. Dersom den står oppført med f.eks C, går du til C (alltid i den siste tabellen), og ser hvilken fra node den står oppført med.. slik fortsetter du til du kommer til F-noden. Disse nodene du nå har gått innom, er korteste vei fra F til A.