Wiki NSI

Ici nous cherchons à connaitre le chemin entre deux noeuds
cet algorithme renvoie un chemin, ce n'est pas forcement le plus court
L'algorithme va renvoyer une chaine de noeud entre le noeud de depart et le noeud d'arrivé

VARIABLE
G : un graphe
start : noeud (noeud de départ)
end : noeud (noeud d'arrivé)
u : noeud
chaine : ensemble de noeuds (initialement vide)

DEBUT
TROUVE-CHAINE(G, start, end, chaine):
  chaine = chaine ⋃ start //le symbol ⋃ signifie union, il permet d'ajouter le noeud start à l'ensemble chaine
  si start est identique à end :
    renvoie chaine
  fin si
  pour chaque sommet u adjacent au sommet start :
    si u n'appartient pas à chaine :
      nchemin = TROUVE-CHAINE(G, u, end, chaine)
      si nchemin non vide :
        renvoie nchemin
      fin si
    fin si
	fin pour
	renvoie NIL
FIN