3 réponses
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
Bonjour,
"je tombe toujours sur des boucles infinies"
peux-tu nous montrer ce que tu as fait ?
L'indentation étant importante en Python, merci de copier/coller ici ton code complet avec les balises de code
mode d'emploi:
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Visuellement, ça doit ressembler à ceci (avec la coloration syntaxique) :
"je tombe toujours sur des boucles infinies"
peux-tu nous montrer ce que tu as fait ?
L'indentation étant importante en Python, merci de copier/coller ici ton code complet avec les balises de code
mode d'emploi:
https://codes-sources.commentcamarche.net/faq/11288-les-balises-de-code
Visuellement, ça doit ressembler à ceci (avec la coloration syntaxique) :
def test():
print('test')
test()
Bonjour,
Si tu as une boucle infinie, essaye de déterminer quelle est la boucle qui tourne indéfiniment. Ajouter un print à différents endroits de l'algorithme peut sans doute t'aider à y voir plus clair.
Pour rappel, l'algorithme de Dijkstra traverse chaque sommet et chaque arc une fois s'il est atteignable depuis le sommet source, zéro sinon. La boucle la plus suspecte est celle qui gère le tas des sommets à visiter. Assure-toi que les sommets rencontrés ne sont bien traités qu'au plus une fois. Tu pourrais ajouter un compteur pour voir combien de fois tu traverses cette boucle. Si cette valeur excède le nombre de sommets du graphe, c'est qu'il y a un problème dans ton omplémentation.
Pour éviter de traiter un sommet plusieurs fois (en particulier s'il est atteignable via plusieurs chemins incidents), on a recours un vecteur qui à chaque sommet associe son état traditionnellement représenté par un vecteur de couleur (blanc = pas encore visité, gris = en cours de visite, noir = visité).
Le pseudo code de l'algorithme est disponible :ici.
Si tu bloques, il faut nous partager ton code et nous dire ce que tu ne comprends pas.
Bonne chance
Si tu as une boucle infinie, essaye de déterminer quelle est la boucle qui tourne indéfiniment. Ajouter un print à différents endroits de l'algorithme peut sans doute t'aider à y voir plus clair.
Pour rappel, l'algorithme de Dijkstra traverse chaque sommet et chaque arc une fois s'il est atteignable depuis le sommet source, zéro sinon. La boucle la plus suspecte est celle qui gère le tas des sommets à visiter. Assure-toi que les sommets rencontrés ne sont bien traités qu'au plus une fois. Tu pourrais ajouter un compteur pour voir combien de fois tu traverses cette boucle. Si cette valeur excède le nombre de sommets du graphe, c'est qu'il y a un problème dans ton omplémentation.
Pour éviter de traiter un sommet plusieurs fois (en particulier s'il est atteignable via plusieurs chemins incidents), on a recours un vecteur qui à chaque sommet associe son état traditionnellement représenté par un vecteur de couleur (blanc = pas encore visité, gris = en cours de visite, noir = visité).
Le pseudo code de l'algorithme est disponible :ici.
Si tu bloques, il faut nous partager ton code et nous dire ce que tu ne comprends pas.
Bonne chance