Dijkstra - Shortest path

Det bedste du kan gøre er at lave en graf på papir og køre den igennem der. Så får du øvelse i algoritmen og så er den helt sikkert nemmere at programmere.

En mulig måde at programmere Dijkstra på:

//Start med den node som er udgangspunktet (v), giv den værdi 0
v.value = 0

//Alle andre noder gives værdi uendelig (dvs. højeste mulige positive værdi).
..

Lav en prioritetskø Q indeholdende alle kanter med deres vægt som key.

while (der er elementer i Q)
  u = q.removeMin()
  for alle noder z, som er nabo til u, og z er i Q
    if (u.value + vægten af kanten u,z) < z.value)
      z.value = u.value + vægten af kanten u,z
      ret z.value i Q til den nye værdi af z

Når dette er udført har grafens noder de værdier som er kortest vej fra udgangspunktet (dvs. node v).

Dvs. din datastruktur skal have mulighed for at gemme en værdi på en node.

kigger på lidt senere... skal lige hjem fra skolen (er hjemme om en times tid).

Men hvis jeg kører med 4 forskellige veje, vil jeg vel skulle "udvide" if-betingelsen eller hvad...?

Det er ligegyldigt.
Dijkstra virker i en graf med cyckler, der må bare ikke være negativ vægt på nogle af kanterne (hvis der er det, skal du bruge en anden algoritme).

Djikstra's er meget god, men hvis du bare skal finde den korteste afstand fra A til B kan du lave andre algorithmer der teoretisk er hurtigere (tilføj noder en efter en til graf, find en path, ignorer alle noder der ville gøre path længere), og hvis du har koordinater på de enkelte noder kan man optimerer det endnu mere (vælg noder efter dem der er fysisk tættest på målet, derefter som første).
Jeg kan dog ikke længere huske hvad disse algorithmer hedder, men måske kan soreno hvis det er aktuelt.

Generelt er Dijkstra en Single Source Shortest Path (SSSP) algoritme. Disse findes der flere af.

Udførselstid (n er antal vertices, m er antal edges) for Dijkstra er O(m + n log n) ved adjacency list repræsentation og Fibonacci heap som prioritets kø.
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

En anden algoritme, der tager højde for negative edges, er Bellman-Ford.
Den har en udførselstid på O(n*m).
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

Hvis grafen er acyklisk kan DAGShortestPaths (en topologisk sortering) benyttes.
Den har en udførselstid på O(n+m) ved adjacency list repræsentation.


At finde korteste vej fra A til B, kan bl.a. gøres ved en:
http://en.wikipedia.org/wiki/A-star_algorithm

Eller muligvis ved en bredde først eller dybde først søgning.

Takker mange gange for jeres hjælp - begge to !

...i må undskylde at jeg ikke lige har fået svaret på jeres indlæg, men jeg har en  Java applikation, der skal være færdig til på mandag, sååå...
(og det her er ren interesse ;o) )

Ved godt at næsten har skåret det ud i pap, men kunne jeg ikke få en af jer til at poste et eksempel, hvor jeg kan se hvor samtlige variabler oprettes/initialiseres etc.. så jeg kan følge det helt fra scratch (har ikke arbejdet med grafer før).

og så må i da gerne smide et svar... ;o)

Jeg har ikke kunne finde et passende graf bibliotek (til Java) som har understøttet det ønskede. Derfor er det umuligt at skrive konkret kode. For koden skal jo afspejle graf interfacet til netop det bibliotek man bruger.