On se base sur une tableau à N éléments indiquant si on a croisé tel sommet ou pas, et sur une liste de sommets pour lesquels on cherche à lister les sommets qui sont liés :
Existe_chemin1 (T, croisés, liste) :
Si liste est vide : renvoyer faux
S «- tête (liste)
Si S = T : renvoyer vrai
Pour i de 1 à N
Si f(S, i) = 1 et croisés[i] = faux :
croisés[i] «- vrai
liste «- empiler (i, liste)
Finsi
Fin pour
Existe_chemin (T, croisés, liste)
Fin
Et on lance le programme avec un tableau 'croisés' rempli de valeur 'faux' (sauf pour S), et 'liste' qui vaut [S].
Pour la seconde question, c'est plus compliqué.
On remarque que, s'il existe un chemin de S à T, on peut choisir U à peu près au milieu du chemin, avant de vérifier qu'il existe un chemin entre S et U puis entre U et T. Pour éviter de faire des boucles, il va falloir retenir les sommets parcourus précédemment. C'est-à-dire qu'on invoquera les fonctions :
Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste)).
Par ce procédé, tant qu'on choisit U de manière optimale, la taille de la liste n'excédera jamais log(N).
Pour éviter de faire exploser la complexité dans le cas où il n'existe pas de chemin entre S et T, il suffit de contrôler la taille de la liste : si elle dépasse log(N) (ou une limite arbitraire un peu au-dessus, comme 2*log(N)), on sait que le choix de U était incorrect, ou alors qu'il n'existe pas de chemin entre S et T.
Ensuite, pour trouver le U correct, comme on a aucun indice nous permettant de le deviner, il suffit de tous les tester (on se fiche de la complexité temporelle). Ça donne :
Existe_chemin2 (S, T, liste)
Si S=T : renvoyer vrai
Si taille(liste) > 2*log(N) : renvoyer faux
U «- 1
résultat «- faux
Tant que U <= N et résultat = faux
résultat «- Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste))
U «- U+1
Fin tant que
Renvoyer résultat
Fin
Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale'), ni à tester toutes les options pour en trouver une bonne au milieu (ça fait exploser la complexité). Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !
# Solution
Posté par Samuel (site web personnel) . En réponse au journal Informatique fondamentale : chemins dans un graphe. Évalué à 8.
On se base sur une tableau à N éléments indiquant si on a croisé tel sommet ou pas, et sur une liste de sommets pour lesquels on cherche à lister les sommets qui sont liés :
Existe_chemin1 (T, croisés, liste) :
Si liste est vide : renvoyer faux
S «- tête (liste)
Si S = T : renvoyer vrai
Pour i de 1 à N
Si f(S, i) = 1 et croisés[i] = faux :
croisés[i] «- vrai
liste «- empiler (i, liste)
Finsi
Fin pour
Existe_chemin (T, croisés, liste)
Fin
Et on lance le programme avec un tableau 'croisés' rempli de valeur 'faux' (sauf pour S), et 'liste' qui vaut [S].
Pour la seconde question, c'est plus compliqué.
On remarque que, s'il existe un chemin de S à T, on peut choisir U à peu près au milieu du chemin, avant de vérifier qu'il existe un chemin entre S et U puis entre U et T. Pour éviter de faire des boucles, il va falloir retenir les sommets parcourus précédemment. C'est-à-dire qu'on invoquera les fonctions :
Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste)).
Par ce procédé, tant qu'on choisit U de manière optimale, la taille de la liste n'excédera jamais log(N).
Pour éviter de faire exploser la complexité dans le cas où il n'existe pas de chemin entre S et T, il suffit de contrôler la taille de la liste : si elle dépasse log(N) (ou une limite arbitraire un peu au-dessus, comme 2*log(N)), on sait que le choix de U était incorrect, ou alors qu'il n'existe pas de chemin entre S et T.
Ensuite, pour trouver le U correct, comme on a aucun indice nous permettant de le deviner, il suffit de tous les tester (on se fiche de la complexité temporelle). Ça donne :
Existe_chemin2 (S, T, liste)
Si S=T : renvoyer vrai
Si taille(liste) > 2*log(N) : renvoyer faux
U «- 1
résultat «- faux
Tant que U <= N et résultat = faux
résultat «- Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste))
U «- U+1
Fin tant que
Renvoyer résultat
Fin
Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale'), ni à tester toutes les options pour en trouver une bonne au milieu (ça fait exploser la complexité). Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !