Question 1: Algorithme de Dijkstra ou DFS, en gros tu parcours ton graph et tu t'arrête dés que tu tombe sur T. On ne te demande même pas le plus courts chemin. Les deux sont en N^2 faut juste une mécanique d'arrêt si T est fermé transitivement.
Question 2: Bon la ca devient plus complex, on a un graph orienté potentiellement cyclique et il s'agit de le parcourir avec une complexité spatial de log(n)^2. Déjà il n'y pas d'algo classique pour ce problème qui viennent a l'esprit immédiatement.
On est pas limité en niveau temporelle donc on peut envisager des solution bien gruick, genre l'exploration aléatoire ( j'ai log(N)^2 explorateur qui parte de S et se balade aléatoirement sur le graph, ont ajout deux trois règles genre pas plus d'un explorateur par sommet, etc ), mais bon on est pas a l'abri d'une belle fermeture transitive qui enferme tous les explorateurs.
Y a peut être des solutions basé sur les tri topologique mais vue que ton graph peut être cyclique ca ne marche pas non plus.
On peut imaginer de tests tous les chemins de longueur log(N)^2 de manière itérative, mais si on a un graph peut dense ou cyclique ca ne marche pas non plus.
La solution m'intéresse, parce qu'a part l'exploration aléatoire j'ai pas d'idée.
# Ma réponse
Posté par Beretta_Vexee . En réponse au journal Informatique fondamentale : chemins dans un graphe. Évalué à 2.
Question 2: Bon la ca devient plus complex, on a un graph orienté potentiellement cyclique et il s'agit de le parcourir avec une complexité spatial de log(n)^2. Déjà il n'y pas d'algo classique pour ce problème qui viennent a l'esprit immédiatement.
On est pas limité en niveau temporelle donc on peut envisager des solution bien gruick, genre l'exploration aléatoire ( j'ai log(N)^2 explorateur qui parte de S et se balade aléatoirement sur le graph, ont ajout deux trois règles genre pas plus d'un explorateur par sommet, etc ), mais bon on est pas a l'abri d'une belle fermeture transitive qui enferme tous les explorateurs.
Y a peut être des solutions basé sur les tri topologique mais vue que ton graph peut être cyclique ca ne marche pas non plus.
On peut imaginer de tests tous les chemins de longueur log(N)^2 de manière itérative, mais si on a un graph peut dense ou cyclique ca ne marche pas non plus.
La solution m'intéresse, parce qu'a part l'exploration aléatoire j'ai pas d'idée.