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 !