cs_xtremiste
Messages postés5Date d'inscriptionmardi 11 mai 2004StatutMembreDernière intervention 9 août 2006
-
9 août 2006 à 20:48
cs_zephyrin
Messages postés47Date d'inscriptionmercredi 29 mai 2002StatutMembreDernière intervention17 août 2006
-
17 août 2006 à 17:05
Bonjour, j’ai quelques problèmes pour vérifier les chemins d’une chaîne de côte d’une pièce.
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.
cs_zephyrin
Messages postés47Date d'inscriptionmercredi 29 mai 2002StatutMembreDernière intervention17 août 2006 17 août 2006 à 17:05
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).