Code : Tout sélectionner
#include <Array.au3>
; principe général : utiliser la représentation des données la plus véloce :
; False / True au lieu de "Non" / "Oui", Null pour "Aucun", entiers et non chaînes, etc.
; liste des villes-étapes.
Global $aVilles = [ _
"Arras", _
"Bordeaux", _
"Brest", _
"Lyon", _
"Marseille", _
"Montpellier", _
"Nantes", _
"Paris", _
"Poitier", _
"Strasbourg" _
]
; Cette liste doit être triée alphabétiquement, sinon on fait :
_ArraySort($aVilles)
Global $iNbVilles = UBound($aVilles) ; un raccourci de langage bien commode
; tableau construit dynamiquement à partir de $aVilles
Global Enum $__Poids, $__Visite
Global $aPoids[$iNbVilles][2] ; poids, parcouru
For $i = 0 To $iNbVilles - 1
$aPoids[$i][$__Poids] = -1
$aPoids[$i][$__Visite] = False
Next
; tableau construit dynamiquement à partir de $aVilles
Global $aAntecedant[$iNbVilles] ; antécédant
For $i = 0 To $iNbVilles - 1
$aAntecedant[$i] = Null
Next
; Cette présentation est un tableau où seules figurent les distances entre villes A et B
Global Enum $__Ville1, $__Ville2, $__Dist
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] _
]
Local $sDepart, $iDepart
Do
$sDepart = InputBox("", "Ville de départ : ")
$iDepart = _ArrayBinarySearch($aVilles, $sDepart)
Until $iDepart <> -1
Local $sArrivee, $iArrivee
Do
$sArrivee = InputBox("", "Ville d'arrivée : ")
$iArrivee = _ArrayBinarySearch($aVilles, $sArrivee)
Until $iArrivee <> -1
$aPoids[$iDepart][$__Poids] = 0 ; poids zéro de ville départ à ville départ
Local $PoidsMin, $iVilleEtape, $iVilleCible
; Tant que le noeud ayant le poids le plus faible n'est pas le noeud d'arrivée.
Do
$PoidsMin = 3e300 ; poids inatteignable
; On cherche le noeud non parcouru avec le poids minimum mais >= 0
For $i = 0 To $iNbVilles - 1
If Not $aPoids[$i][$__Visite] And $aPoids[$i][$__Poids] >= 0 And $aPoids[$i][$__Poids] < $PoidsMin Then
$PoidsMin = $aPoids[$i][$__Poids]
$iVilleEtape = $i
EndIf
Next
$aPoids[$iVilleEtape][$__Visite] = True ; parcouru
If $iVilleEtape = $iArrivee Then ExitLoop
ConsoleWrite(@LF & "Etape de " & $aVilles[$iVilleEtape] & ", " & $aPoids[$iVilleEtape][$__Poids] & " km parcourus." & @LF)
; on explore toutes les liaisons possibles depuis la ville étape où l'on n'est pas déjà allé
For $i = 0 To UBound($aDistance) - 1
$iVilleCible = -1
If $aDistance[$i][$__Ville1] = $iVilleEtape Then $iVilleCible = $aDistance[$i][$__Ville2]
If $aDistance[$i][$__Ville2] = $iVilleEtape Then $iVilleCible = $aDistance[$i][$__Ville1]
If $iVilleCible >= 0 Then
ConsoleWrite("Liaison " & $aVilles[$iVilleEtape] & ' --> ' & $aVilles[$iVilleCible] & " : ")
; les noeuds fils de notre ville-étape défilent
; pour chacun, on vérifie qu'on n'est pas déjà passé par là
; ET que
; (poids de noeud fils non défini OU
; poids de noeud fils > poids de noeud père + distance noeud père-noeud fils)
If Not $aPoids[$iVilleCible][$__Visite] Then
If ($aPoids[$iVilleCible][$__Poids] < 0 Or _
$aPoids[$iVilleCible][$__Poids] > $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist]) Then
; alors poids de noeud fils = poids de noeud père + distance noeud père-noeud fils et l'antécédant de noeud fils est noeud père
$aPoids[$iVilleCible][$__Poids] = $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist]
$aAntecedant[$iVilleCible] = $iVilleEtape
ConsoleWrite("étape potentielle." & @LF)
ConsoleWrite("Poids " & $aVilles[$iVilleCible] & " = " & $aPoids[$iVilleCible][$__Poids] & " # " & $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist] & @LF)
Else
ConsoleWrite("ville trop éloignée." & @LF)
ConsoleWrite("Poids " & $aVilles[$iVilleCible] & " = " & $aPoids[$iVilleCible][$__Poids] & " # " & $aPoids[$iVilleEtape][$__Poids] + $aDistance[$i][$__Dist] & @LF)
EndIf
Else
ConsoleWrite("ville déjà parcourue." & @LF)
EndIf
EndIf
Next
; sortie de boucle si l'on est arrivés
Until False
Local $sEtapes = $aVilles[$iArrivee]
Local $iVille = $iArrivee
Do
$iVille = $aAntecedant[$iVille]
$sEtapes = $aVilles[$iVille] & ', ' & $sEtapes
Until $iVille = $iDepart
ConsoleWrite(@LF & "Le plus court itinéraire (" & $aPoids[$iArrivee][$__Poids] & " km) de " & $aVilles[$iDepart] & " à " & $aVilles[$iArrivee] & " est : " & $sEtapes & @LF)
!
! Merci pour tout!!!
