Code ne trouve pas un résultat (qui existe pourtant!)

Bonsoir à tous, j'espère que vous allez bien avec les conditions actuelles. Je me casse la tête depuis plusieurs jours car mon code bug et je ne comprends pas pourquoi.

J’ai une feuille avec des résultats de l’algorithme de Dijkstra sur le calcul du plus court chemin entre 2 nœuds s et t d'un graph. J’ai bien réussi cette partie et maintenant je dois extraire le chemin utilisé pour aller du nœud s à t (ici, s= 21 et t= 9, mais c'est censé fonctionner pour n'importe quel nœud t).

Vu que j’ai le tableau des labels (label(i) = plus court chemin du nœud s au nœud i) il me suffit de partir du nœud t et de chercher parmi ses prédécesseurs celui dont le label correspond à label (t) – distance (i,t) (tableau 2 colonne 4) et ainsi de suite.

Mon code s’exécute bien mais se bloque à un moment (au nœud 67 dans ce cas) pourtant il est censé trouver le nœud 38 comme prédécesseur. Pouvez-vous m’aider à comprendre pourquoi svp ?

J'ai mis ma feuille avec le schéma du graph en pj.

Bonjour,

Le code bloquait à deux endroits car u=0 ... d'où l'erreur.

Un essai ...

Sub PCC_Dijkstra()
        'Call Dijkstra(Range("P6").Value, Range("P7").Value)
        'Recuprération du chemin
Dim Chemin As Range
Dim index()
Dim arcs()
Dim label()
Dim u As Integer
Dim d As Integer
Dim f As Integer
Dim i As Integer
Dim rw As Range

    With Worksheets("Feuil1")
        Set Chemin = .Range("P17:P89")
        i = 1
        For Each rw In Chemin.Rows
            If u = .Range("P6").Value Then
                Exit For
            Else
                If i = 1 Then
                    rw.Value = .Range("P7").Value
                    i = i + 1
                Else
                    index() = .Range("A2:D73").Value         'Tab_1
                    arcs() = .Range("F2:I255").Value         'Tab_2
                    label() = .Range("K2:M73").Value         'Tab_3

                    u = Chemin.Cells(i - 1, 1).Value
                    If u > 0 Then       ' éviter que u = 0
                        d = index(u, 3)
                        f = index(u, 4)
                    End If
                    For k = d To f
                        If u > 0 Then   'éviter que u = 0
                            If label(u, 2) - arcs(k, 4) = label(arcs(k, 3), 2) Then rw.Value = arcs(k, 3)
                        End If
                    Next
                    i = i + 1
                End If
            End If
        Next rw
    End With
End Sub

ric

Merci pour votre aide Ric,

mais j'avais déjà essayé quelque chose de similaire pour empêcher les zéro, mais là ça arrête le code après le nœud 67. Pourtant le code devrait continuer et trouver 38 puis 32 puis 25... bref le chemin n'est pas terminé tant qu'il n'arrive pas à 21 et je ne comprends pas pourquoi il ne me trouve pas ces résultats...

Bonjour,

Il arrête à la valeur 67 car, lors du test de comparaison,

If label(u, 2) - arcs(k, 4) = label(arcs(k, 3), 2) Then

If 14,9609315100724<>14,9609315100724 = vrai ce qui est faux.

J'ai fait afficher avec 30 décimales.

J'ai trouvé le souci, il reste à trouver ce qui se passe et comment corriger

ric

Merci encore Ric, mais j'ai réfléchit à une toute autre méthode qui n'utilise pas ce code finalement mais qui apporte juste quelques modif à mon implémentation de Dijkstra, et ça fonctionne très bien.

Merci pour ton aide!

Bonjour,

Tant mieux si le souci n'est plus sous ci.

Je vais donc cesser de me tourmenter à tenter de comprendre la chose.

Mais je ne suis pas sûr que ce soit le code qui soit fautif, car, il fonctionne bien sur les 7 premiers pas.

Je soupçonne une coquille dans les données sources.

J'ai fait copier

rw.Offset(, 1).Value = label(u, 2)
rw.Offset(, 2).Value = arcs(k, 4)
rw.Offset(, 3).Value = label(arcs(k, 3), 2)

Afin que l'équation soit bonne au 8e pas ... 20,855086912504200-1,604534924645230=22,459621837149400

Mais, l'on constate qu'il faut additionner au lieu de soustraire. Ce qui est contraire aux pas précédents.

20,855086912504200+1,604534924645230=22,459621837149400

C'est ce qui me fait douter de l'intégrité des données sources.

M'enfin, tu as une solution différente qui te convient. C'est cela l'important.

ric