Dijkstra - Kürzester Weg

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Dijkstra - Kürzester Weg

Beitrag von remi_meier »

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
Benutzeravatar
Vallan
Beiträge: 223
Registriert: 20.01.2006 19:34
Kontaktdaten:

Beitrag von Vallan »

Wie wär's mit ner visualisirung?
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag von remi_meier »

Warum?
Benutzeravatar
Macros
Beiträge: 1314
Registriert: 23.12.2005 15:00
Wohnort: Olching(bei FFB)
Kontaktdaten:

Beitrag von Macros »

Dann sieht man, was das Programm macht,
sieht enfach hübscher aus.
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag von remi_meier »

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 :allright:
Benutzeravatar
Xaby
Beiträge: 2144
Registriert: 12.11.2005 11:29
Wohnort: Berlin + Zehdenick
Kontaktdaten:

Beitrag von Xaby »

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 :roll:
Kinder an die Macht http://scratch.mit.edu/
Benutzeravatar
remi_meier
Beiträge: 1078
Registriert: 29.08.2004 20:11
Wohnort: Schweiz

Beitrag von remi_meier »

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 :D
Benutzeravatar
DrShrek
Beiträge: 1970
Registriert: 08.09.2004 00:59

Beitrag von DrShrek »

remi_meier hat geschrieben:..., aber die anderen Freunde
können dir ev. helfen :D
Hihi... Der war lustig! Hihi...
Siehste! Geht doch....?!
PB*, *4PB, PetriDish, Movie2Image, PictureManager, TrainYourBrain, ...
Benutzeravatar
KatSeiko
Beiträge: 367
Registriert: 19.07.2008 07:47

Beitrag von KatSeiko »

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...
Win7 Ultimate x64, PureBasic 5.11

There is no substitute..
BildBildBild
Benutzeravatar
Froggerprogger
Badmin
Beiträge: 855
Registriert: 08.09.2004 20:02

Beitrag von Froggerprogger »

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... :)
!UD2
Antworten