Chemin dans un graphique

Résolu
Messages postés
5
Date d'inscription
mardi 11 mai 2004
Statut
Membre
Dernière intervention
9 août 2006
-
Messages postés
47
Date d'inscription
mercredi 29 mai 2002
Statut
Membre
Dernière intervention
17 août 2006
-
Bonjour, j’ai quelques problèmes pour vérifier les chemins d’une chaîne de côte d’une pièce.



<?xml:namespace prefix v ns "urn:schemas-microsoft-com:vml" /??>
<v:shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600">
<v:stroke joinstyle="miter">
</v:stroke>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0">
</v:f>
<v:f eqn="sum @0 1 0">
</v:f>
<v:f eqn="sum 0 0 @1">
</v:f>
<v:f eqn="prod @2 1 2">
</v:f>
<v:f eqn="prod @3 21600 pixelWidth">
</v:f>
<v:f eqn="prod @3 21600 pixelHeight">
</v:f>
<v:f eqn="sum @0 0 1">
</v:f>
<v:f eqn="prod @6 1 2">
</v:f>
<v:f eqn="prod @7 21600 pixelWidth">
</v:f>
<v:f eqn="sum @8 21600 0">
</v:f>
<v:f eqn="prod @7 21600 pixelHeight">
</v:f>
<v:f eqn="sum @10 21600 0">
</v:f>
</v:formulas>
<v:path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f">
</v:path>
<?xml:namespace prefix o ns "urn:schemas-microsoft-com:office:office" /??>
<o:lock aspectratio="t" v:ext="edit">

</o:lock>
</v:shapetype>


Pour la côte de fabrication F1 : on doit partir de l’extrémité de celle-ci et trouver le chemin permettant de revenir à l’origine de la flèche. Soit



 




F1 = chemin F2 ; F3 ; F4 ou F5 ; F4


F2= chemin F6 ; F1 ou F3 ; F4 ; F1…..



 




Je me moque de la longueur du chemin, par contre je ne dois pas passer 2 fois sur la même côte. Je fais apparaître un message d’erreur si <?xml:namespace prefix st1 ns "urn:schemas-microsoft-com:office:smarttags" /??><st1:personname w:st="on" productid="la Fi">la Fi</st1:personname> n’appartient pas à un chemin.



 




J’ai commencé par resancer les possibilités après chaque flèche que j’ai stocké dans un tableau.



 




Soit F1 : on a le choix en F2 ou F3


Soit F2 : on a le choix en F3 ou F6…



 




Le problème est que je n’arrive pas à effectuer une boucle me permettant de vérifier l’ensemble des chemins.


J’ai une cascade de for et if, ce qui devient ingérable avec une centaine de flèches



 




For i = 1 to nbreFelche



            If  Fi a un voisin



                        For i1 = 1 to nbreFelche



                                   If……



                        Next i1



            End if


Next i



 




J’ai regardé l’algorithme de Dijkstra, mais je n’arrive pas à l’appliquer. Si vous avez l’algorithme nécessaire, je suis preneur.


Merci et bonne soirée.


Steph

1 réponse

Messages postés
47
Date d'inscription
mercredi 29 mai 2002
Statut
Membre
Dernière intervention
17 août 2006

salut,
il te suffit de faire une fonction récursive de parcours de ton graphe.
Tu trouveras le plus bel exemple en cherchant l'algo du "voyageur de commerce" qui en plus te donnera le chemin le plus court (pas le code sous la main).

Zephyrin