Bonjour,
Je dois determiner s'il existe un chemin entre un etat initial et un etat final tel qu'un de ses arcs appartient à un circuit.
existe il un algorithme pour faire çà ? quel est son nom ?
sinon est ce une bonne idée de calculer d'abord la fermeture reflexo-transitive du graphe ( G=(S,A), la fermeture reflexo transitive de G est notée Gt=(S,At) et elle verifie: { (x,y) appartient At <=> il existe un chemin [x,y] dans G})
et de chercher ensuite un circuit dans ce graphe ?
l'algorithme doit avoir la meilleur complexité possible.
Partager