[..] Dijkstra(encore)
Posté : ven. 26 juin 2015 20:54
par sozary
Bonsoir à tous!
Alors voilà, j'ai réessayé de faire un algorithme dijkstra comme sur le site http://openclassrooms.com/courses/le-pa ... c-dijkstra.
La dernière fois, j'avais eu recourt à votre aide, mais là je suis dans un cas que je ne comprends pas.
Mon algorithme est défaillant, mais je ne sais pas où, et croyez moi j'ai cherché!
Bon alors je sais que le code est loin d'être clean, mais pourriez vous me dire d'où viens l'erreur svp?
P-S: Mikell, ne t’inquiète pas je bosse sur la traduction aussi
!
Alors voilà, j'ai réessayé de faire un algorithme dijkstra comme sur le site http://openclassrooms.com/courses/le-pa ... c-dijkstra.
La dernière fois, j'avais eu recourt à votre aide, mais là je suis dans un cas que je ne comprends pas.
Mon algorithme est défaillant, mais je ne sais pas où, et croyez moi j'ai cherché!
► Afficher le texte
Code : Tout sélectionner
#include <array.au3>
#Region variables
Global $aVilles = [ _
"Arras", _
"Bordeaux", _
"Brest", _
"Lyon", _
"Marseille", _
"Montpellier", _
"Nantes", _
"Paris", _
"Poitier", _
"Strasbourg" _
]
_ArraySort($aVilles)
Global $aDistance = [ _ ; départ, cible, distance
[_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Nantes"), 561], _
[_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Paris"), 185], _
[_ArrayBinarySearch($aVilles, "Arras"), _ArrayBinarySearch($aVilles, "Strasbourg"), 522], _
[_ArrayBinarySearch($aVilles, "Bordeaux"), _ArrayBinarySearch($aVilles, "Nantes"), 334], _
[_ArrayBinarySearch($aVilles, "Bordeaux"), _ArrayBinarySearch($aVilles, "Poitier"), 237], _
[_ArrayBinarySearch($aVilles, "Brest"), _ArrayBinarySearch($aVilles, "Nantes"), 298], _
[_ArrayBinarySearch($aVilles, "Brest"), _ArrayBinarySearch($aVilles, "Paris"), 593], _
[_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Marseille"), 315], _
[_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Montpellier"), 303], _
[_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Paris"), 465], _
[_ArrayBinarySearch($aVilles, "Lyon"), _ArrayBinarySearch($aVilles, "Strasbourg"), 494], _
[_ArrayBinarySearch($aVilles, "Marseille"), _ArrayBinarySearch($aVilles, "Montpellier"), 171], _
[_ArrayBinarySearch($aVilles, "Marseille"), _ArrayBinarySearch($aVilles, "Strasbourg"), 809], _
[_ArrayBinarySearch($aVilles, "Montpellier"), _ArrayBinarySearch($aVilles, "Poitier"), 557], _
[_ArrayBinarySearch($aVilles, "Montpellier"), _ArrayBinarySearch($aVilles, "Strasbourg"), 797], _
[_ArrayBinarySearch($aVilles, "Nantes"), _ArrayBinarySearch($aVilles, "Paris"), 386], _
[_ArrayBinarySearch($aVilles, "Paris"), _ArrayBinarySearch($aVilles, "Poitier"), 338] _
]
Global $Antecedants = [ _
["Arras", "Aucun"], _
["Bordeaux", "Aucun"], _
["Poitier", "Aucun"], _
["Strasbourg", "Aucun"], _
["Brest", "Aucun"], _
["Lyon", "Aucun"], _
["Marseille", "Aucun"], _
["Montpellier", "Aucun"], _
["Nantes", "Aucun"], _
["Paris", "Aucun"] _
]
Global $Parkour = [ _
["Arras", -1, "non"], _
["Bordeaux", -1, "non"], _
["Brest", -1, "non"], _
["Poitier", -1, "non"], _
["Strasbourg", -1, "non"], _
["Lyon", -1, "non"], _
["Marseille", -1, "non"], _
["Montpellier", -1, "non"], _
["Nantes", -1, "non"], _
["Paris", -1, "non"] _
]
Global $VilleDepart = "Bordeaux", $VilleArrivee = "Strasbourgs", $VilleCourante = $VilleDepart, $chemin = ""
Global $anciens[0]
#EndRegion variables
$Parkour[_ArraySearch($Parkour, $VilleDepart)][1] = 0
$Parkour[_Arraysearch($Parkour, $VilleDepart)][2] = "oui"
While 1
If $VilleCourante = $VilleArrivee Then ExitLoop
For $i = 0 To UBound($aDistance) - 1
Switch $VilleCourante
Case $aVilles[$aDistance[$i][0]]
$VilleFille = $aVilles[$aDistance[$i][1]]
If $Parkour[_ArraySearch($Parkour, $VilleFille)][2] = "non" Then
If $Parkour[_ArraySearch($Parkour, $VilleFille)][1] > $Parkour[_ArraySearch($Parkour, $VilleCourante)][1] + $aDistance[$i][2] Or $Parkour[_ArraySearch($Parkour, $VilleFille)][1] = -1 Then
$Parkour[_ArraySearch($Parkour, $VilleFille)][1] = $Parkour[_ArraySearch($Parkour, $VilleCourante)][1] + $aDistance[$i][2]
$Antecedants[_ArraySearch($Antecedants, $VilleFille)][1] = $VilleCourante
_ArrayAdd($anciens, $VilleFille)
EndIf
EndIf
Case $aVilles[$aDistance[$i][1]]
$VilleFille = $aVilles[$aDistance[$i][0]]
If $Parkour[_ArraySearch($Parkour, $VilleFille)][2] = "non" Then
If $Parkour[_ArraySearch($Parkour, $VilleFille)][1] > $Parkour[_ArraySearch($Parkour, $VilleCourante)][1] + $aDistance[$i][2] Or $Parkour[_ArraySearch($Parkour, $VilleFille)][1] = -1 Then
$Parkour[_ArraySearch($Parkour, $VilleFille)][1] = $Parkour[_ArraySearch($Parkour, $VilleCourante)][1] + $aDistance[$i][2]
$Antecedants[_ArraySearch($Antecedants, $VilleFille)][1] = $VilleCourante
_ArrayAdd($anciens, $VilleFille)
EndIf
EndIf
EndSwitch
Next
_ArrayDisplay($Parkour)
$Index = Min($Parkour, 1)
$VilleCourante = $Parkour[$Index][0]
ReactualliseAncien($anciens)
WEnd
$chemin = ReformeChemin($Antecedants)
MsgBox(0, "", $chemin)
Func ReformeChemin($Tab)
Local $VilleCourante = $VilleArrivee, $VilleFille = "", $path = ""
While 1
If $VilleCourante = $VilleDepart Then ExitLoop
$path = $VilleCourante & ", " & $path
$VilleCourante = $Antecedants[_ArraySearch($Antecedants, $VilleCourante)][1]
WEnd
Return StringTrimRight($path, 2) & " (" & $Parkour[_ArraySearch($Parkour, $VilleArrivee)][1] & " kilomètres)."
EndFunc ;==>ReformeChemin
Func ReactualliseAncien($anciens)
For $i = 0 To UBound($anciens) - 1
$Parkour[_ArraySearch($Parkour, $anciens[$i])][2] = "oui"
Next
ReDim $anciens[0]
EndFunc ;==>ReactualliseAncien
Func Min($array, $col)
$min = 1e9
For $i = 0 To UBound($array) - 1
If $array[$i][$col] <= $min And $array[$i][$col] >= 0 And $array[$i][$col + 1] = "non" Then $min = $array[$i][$col]
Next
Return _ArraySearch($array, $min, 0, 0, 0, 0, 0, $col)
EndFunc ;==>Min
Bon alors je sais que le code est loin d'être clean, mais pourriez vous me dire d'où viens l'erreur svp?
P-S: Mikell, ne t’inquiète pas je bosse sur la traduction aussi
!
ou, peut être à 