j'ai trouvé ce code sur le forum Allemand,
http://forums.purebasic.com/german/view ... f=8&t=3759
J'ai essayé de développer mon propre code a partir de tuto mais je dois avouer que j'ai atteinds mes limites
Est-ce quelqu'un a une idée pourquoi le résultat n'est pas bon ?
Merci d'avance
Code : Tout sélectionner
#N = 8 ; Num. Noeud
#M = 99999 ; = infini
; Longueur des arcs entre les nœuds
Dim Boegen.l(#N - 1, #N - 1)
Restore distanzen
For y = 0 To #N - 1
For x = 0 To #N - 1
Read.l Boegen(x, y)
Next
Next
; Démarrer et arrêter le nœud
StartK = 0
StopK = 5
; ; Distances par rapport au nœud de départ
Dim Distanz(#N - 1)
; Prédécesseur du nœud
Dim Vorgaenger(#N - 1)
; Noeuds où vous connaissez déjà le chemin le plus court
Dim Markierte(#N - 1)
For z = 0 To #N - 1
Markierte(z) = #False
Next
; Nœud de départ déjà visité!
Markierte(StartK) = #True
; Distance par rapport à vous-même = 0
Distanz(StartK) = 0
; Prédécesseurs d'eux-mêmes
Vorgaenger(StartK) = StartK
; Définissez les distances et les prédécesseurs pour tous les autres nœuds.
For z = 0 To #N - 1
; ausser Startknoten (s.o.)
If z <> StartK
Distanz(z) = Boegen(StartK, z)
Vorgaenger(z) = StartK
EndIf
Next
; Tant que le court. Chemin vers le noeud cible introuvable
While Markierte(StopK) = #False
; Trouvez la distance la plus courte pour les nœuds qui ne sont pas marqués
MinK = -1
MinD = #M
For z = 0 To #N - 1
; Si non marqué
If Markierte(z) = #False
; sidistance plus courte
If Distanz(z) < MinD
MinK = z
MinD = Distanz(z)
EndIf
EndIf
Next
; Si aucun plus court n'a été trouvé (ie distance = infini) -> aucun chemin disponible
If MinD = #M
Debug "Il n'y a pas de connexion entre StartK et StopK"
Break
ElseIf MinK = StopK
; Dle plus court trouvé
Debug "Gefunden"
Break
Else
; Marquez-le, donc un moyen le plus court a été trouvé
Markierte(MinK) = #True
EndIf
; Pour tous les nœuds non marqués: vérifiez s'il existe un chemin plus court via MinK
For z = 0 To #N - 1
If Markierte(z) = #False
; Si le détour par MinK est plus court que l'itinéraire direct
If Distanz(MinK) + Boegen(MinK, z) < Distanz(z)
; Calculer la nouvelle longueur de chemin
Distanz(z) = Distanz(MinK) + Boegen(MinK, z)
; Enregistrez le détour à 'z'
Vorgaenger(z) = MinK
EndIf
EndIf
Next
Wend
If MinK = StopK
; Retracer le chemin depuis le StopK
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:
;-https://www.geeksforgeeks.org/wp-content/uploads/Fig-11.jpg
; 0 1 2 3 4 5 6 7 8
Data.l 0, 4, #M, #M, #M, #M, #M, 8, #M ;0
Data.l 4, 0, 8, #M, #M, #M, #M, 11, #M ;1
Data.l #M, 8, 0, 7, #M, 4, #M, #M, 2 ;2
Data.l #M,#M, 7, 0, 9, 14, #M, #M, #M ;3
Data.l #M,#M, #M, 9, 0, 10, #M, #M, #M ;4
Data.l #M, #M, 4, 14, 10, 0, 2, #M, #M ;5
Data.l #M, #M, #M, #M, #M, 2, 0, 1, #M ;6
Data.l 8, 11, #M, #M, #M, #M, 1, 0, 7 ;7
Data.l #M, #M, 2, #M, #M, #M, 6, 7, 0 ;8
EndDataSection
