PureBoard

Verfasst: **21.06.2005 19:36**

Die Umsetzung des Dijkstra-Algorithmus zum finden des kürzesten Weges
zwischen 2 Punkten in einem Graphen.

Quelle: Buch: "Das Geheimnis des kürzesten Weges" von P. Gritzmann &
R. Brandenburg

Code: Alles auswählen

#N = 4  ; Anz. Knoten

#M = 99999  ; = unendlich
; Länge der Bögen zwischen den Knoten
Dim Boegen.l(#N - 1, #N - 1)

Restore distanzen
For y = 0 To #N - 1
  For x = 0 To #N - 1
    Read Boegen(x, y)
  Next
Next


; Start- und Stopknoten
StartK = 0
StopK  = 3

; Distanzen zum Startknoten
Dim Distanz(#N - 1)

; Vorgänger der Knoten
Dim Vorgaenger(#N - 1)

; Knoten, wo man schon den kürzesten Weg kennt
Dim Markierte(#N - 1)
For z = 0 To #N - 1
  Markierte(z) = #False
Next

; Startknoten schon besucht!
Markierte(StartK) = #True
; Distanz zu sich selber = 0
Distanz(StartK) = 0
; Vorgänger von sich selber
Vorgaenger(StartK) = StartK

; Für alle anderen Knoten die Distanzen und Vorgänger setzen
For z = 0 To #N - 1
  ; ausser Startknoten (s.o.)
  If z <> StartK
    Distanz(z)    = Boegen(StartK, z)
    Vorgaenger(z) = StartK
  EndIf
Next


; Solange der kürz. Weg zum Zielknoten nicht gefunden
While Markierte(StopK) = #False
  ; Finde kürzeste Distanz bei nicht markierten Knoten
  MinK = -1
  MinD = #M
  For z = 0 To #N - 1
    ; Wenn nicht markiert
    If Markierte(z) = #False
      ; Wenn kürzere Distanz
      If Distanz(z) < MinD
        MinK = z
        MinD = Distanz(z)
      EndIf
    EndIf
  Next
  
  
  ; Wenn kein kürzester Gefunden wurde (also Distanz = unendlich) -> kein Weg vorhanden
  If MinD = #M
    Debug "Es gibt keine Verbindung zwischen StartK und StopK"
    Break
    
  ElseIf MinK = StopK
    ; Der kürzeste Weg gefunden
    Debug "Gefunden"
    Break
    
  Else
    ; Markiere ihn, also wurde ein kürzester Weg gefunden
    Markierte(MinK) = #True
  EndIf
  
  
  ; Für alle nicht markierten Knoten: überprüfe, ob über MinK kürzerer Weg existiert
  For z = 0 To #N - 1
    If Markierte(z) = #False
      ; Wenn Umweg über MinK kürzer als Direktweg
      If Distanz(MinK) + Boegen(MinK, z) < Distanz(z)
        ; Neue Weglänge berechnen
        Distanz(z)    = Distanz(MinK) + Boegen(MinK, z)
        ; Umweg bei 'z' einschreiben
        Vorgaenger(z) = MinK
      EndIf
    EndIf
  Next
  
Wend


If MinK = StopK
  ; Zurückverfolgung des Weges vom StopK aus
  s.s  = Str(StopK)
  z    = MinK
  While Vorgaenger(z) <> StartK
    s = Str(Vorgaenger(z)) + ", " + s
    z = Vorgaenger(z)
  Wend
  s = Str(Vorgaenger(z)) + ", " + s
  
  Debug s
  Debug "Distanz: " + Str(Distanz(StopK))
EndIf




DataSection
distanzen:
Data.l 0, 2, 4, #M
Data.l 2, 0, 1, 7
Data.l 4, 1, 0, 3
Data.l #M,7, 3, 0
EndDataSection

greetz
Remi

Verfasst: **14.04.2006 11:22**

Wie wär's mit ner visualisirung?

Verfasst: **15.04.2006 20:59**

Warum?

Verfasst: **15.04.2006 21:12**

Dann sieht man, was das Programm macht,
sieht enfach hübscher aus.

Verfasst: **15.04.2006 21:19**

Das ist mir zu wenig Ansporn. Wenn man Google anwirft und Dijkstra ein-
gibt, findet man genug Visualisierungen. Ich werde sicher keine bessere
hinkriegen. Aber du darfst gerne den Code visualisieren

Verfasst: **18.04.2006 19:33**

Hei Freunde, wie wär's, wenn man den Code mit meinem Problem verknüpft? Die Kamera sieht zwei Punkte und ... naja, vielleicht geht da was ...

Wäre das Ansporn für eine Visualisierung

Verfasst: **18.04.2006 19:43**

Wenn du zwei Punkte siehst, kannst du die auch ohne kürzesten Weg
einfach so verbinden. Ich glaube, da wäre eher noch ein Algorithmus
zum finden konvexer Hüllen etwas. Oder von mir aus ein Rundreise-
algorithmus.

Ich habe leider im Moment keine Zeit dafür, aber die anderen Freunde
können dir ev. helfen

Verfasst: **18.04.2006 20:43**

remi_meier hat geschrieben:..., aber die anderen Freunde
können dir ev. helfen

Hihi... Der war lustig! Hihi...

Verfasst: **25.08.2008 21:59**

Hmm... Irgendwie kann ich das nicht wirklich nachvollziehen. Wie wende ich das auf z.B. ein zweidimensionales Array mit z.B. 16x16 an? Ich hab zumindest gehört, dass Dijkstra der beste Weg ist, um z.B. den kürzesten Weg zwischen einem Erntefahrzeug zu einem Rohstoff-Feld zu finden...

Verfasst: **26.08.2008 07:34**

Der Algorithmus findet den kürzesten Weg (mit geringstem Kantengewicht) zwischen zwei Punkten in einem gerichteten Graphen. Man muss also sein Problem nur als einen solchen darstellen, und dann in eine Eingabe für den Algorithmus umwandeln dort heißt es:

Code: Alles auswählen

#N = 4  ; Anz. Knoten

#M = 99999  ; = unendlich
; Länge der Bögen zwischen den Knoten
Dim Boegen.l(#N - 1, #N - 1)

Die Knoten werden also nur über ihre Anzahl und ihre ID codiert. Die Kanten mit ihren Gewichten durch einen Eintrag in Boegen.l. Dabei entspricht wohl Boegen.l(A, B)=X einem Weg von Knoten A zu Knoten B mit Gewicht X. Diese Codierung in Form einer sog. Adjazenzmatrix hat den Nachteil, sehr speicherintensiv zu sein, dazu ein Beispiel: In einem 16x16-Array einer Tilemap hat man also 256 Knoten und man muss die Kantengewichte definieren, z.B. sollte es nur zu nicht benachbarten Feldern keine Verbindung geben, ebenso keine zu einem gesperrten Feld, also jeweils Gewicht #M in Boegen. Das Array Boegen ist aber schon 256*256*4 Bytes groß. und wächst quadratisch mit der Anzahl Knoten weiter.

Man kann Dijkstra aber auch so abwandeln, dass der Graph in Form einer Adjazenzliste (klingt schlimmer, als es ist) codiert ist. Das spart bei dünnbesetzten Graphen enorm Speicherplatz. Und bei einer Tilemap könnte man ganz anders vorgehen, um den Dijkstra zu implementieren, da man die Kantengewichte direkt aus dem Bodenmatrial des Tiles ablesen könnte und zudem genau weiß, wo und wo nicht eine 'Kante' verläuft. Naja, nur so als Anreiz für eigene Grübeleien...

PureBoard

Dijkstra - Kürzester Weg

Dijkstra - Kürzester Weg