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
Remi