[..] Dijkstra(encore)

Aide et conseils concernant AutoIt et ses outils.
Règles du forum
.
Répondre
Avatar du membre
sozary
Niveau 6
Niveau 6
Messages : 274
Enregistré le : lun. 20 janv. 2014 19:17
Status : Hors ligne

[..] Dijkstra(encore)

#1

Message 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é!
► Afficher le texte


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 :o !
"Là où la volonté est grande, les difficultés diminuent.", Niccolò Machiavelli
MdParadis
Niveau 1
Niveau 1
Messages : 1
Enregistré le : jeu. 25 janv. 2018 20:56
Status : Hors ligne

Re: [..] Dijkstra(encore)

#2

Message par MdParadis »

Bonjour,
Une simple erreur dans le nom de la ville d'arrivée
Global $VilleDepart = "Bordeaux", $VilleArrivee = "Strasbourgs"

Cordialement
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [..] Dijkstra(encore)

#3

Message par jchd »

sozary était en apnée, en attente de la solution depuis fin juin 2015. Merci d'avoir enfin fourni la réponse à son squelette.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
walkson
Modérateur
Modérateur
Messages : 1020
Enregistré le : ven. 12 août 2011 19:49
Localisation : Hurepoix
Status : Hors ligne

Re: [..] Dijkstra(encore)

#4

Message par walkson »

jchd, vos réponses me font souvent rire !
Mais je crains pour MdParadis ou pour sozary que la solution ne soit pas trouvée !
Si la correction de MdParadis permet d'obtenir le même résultat que Openclassrooms, si on change $VilleDepart = "Bordeaux" en une autre ville, BUG !!!
Il y a donc un problème à résoudre que je laisse à MdParadis :P ou, peut être à jchd :mrgreen:
Cordialement,
Walkson
"Horas non numero nisi serenas " Le canon de midi
(Je ne compte que les heures heureuses)
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [..] Dijkstra(encore)

#5

Message par jchd »

Merci mais j'ai malencontreusement d'autres graphes à fouetter tâches qui "crient famine".
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
A2Energie
Niveau 5
Niveau 5
Messages : 140
Enregistré le : ven. 15 nov. 2013 20:22
Status : Hors ligne

Re: [..] Dijkstra(encore)

#6

Message par A2Energie »

Vachement instructif cette méthode.
Merci pour le partage,

$Index = Min($Parkour, 1)
Min renvoi la valeur -1 ce qui est impossible dans le tableau : $Parkour[$Index][0]

La solution peut être de vérifier les valeurs avant de lancer le programme :
#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

If _Arraysearch($Parkour, $VilleArrivee) = -1 Or _ArraySearch($Parkour, $VilleDepart) = -1 Then
   If _Arraysearch($Parkour, $VilleArrivee) = -1 Then MsgBox(0, "Veuillez vérifier et redéfinir la ville", "Ville définie incorrecte :" & @CRLF & "Ville d'arrivée : " & $VilleArrivee)
   If _Arraysearch($Parkour, $VilleCourante) = -1 Then MsgBox(0, "Veuillez vérifier et redéfinir la ville", "Ville définie incorrecte :" & @CRLF & "Ville de départ : " & $VilleCourante)
   Exit
EndIf

$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
Répondre