Trouver tous les chemins entre deux nœuds du graphe

Question

Je travaille sur une implémentation de l'algorithme de Dijkstras pour récupérer le chemin le plus court entre les nœuds interconnectés sur un réseau de routes. J'ai l'implémentation qui fonctionne. Il renvoie tous les chemins les plus courts vers tous les nœuds lorsque je passe le nœud de départ dans l'algorithme.

Ma question: Comment faire pour récupérer tous les chemins possibles du nœud A pour dire le nœud G ou même tous les chemins possibles du nœud A et revenir au nœud A

Answer 1

Voici un algorithme trouvant et imprimant tous les chemins de s à t en utilisant la modification de DFS. La programmation dynamique peut également être utilisée pour trouver le nombre de tous les chemins possibles. Le pseudo-code ressemblera à ceci :

 AllPaths(G(V,E),s,t)
 C[1...n]    //array of integers for storing path count from 's' to i
 TopologicallySort(G(V,E))  //here suppose 's' is at i0 and 't' is at i1 index

  for i<-0 to n
      if i<i0
          C[i]<-0  //there is no path from vertex ordered on the left from 's' after the topological sort
      if i==i0
         C[i]<-1
      for j<-0 to Adj(i)
          C[i]<- C[i]+C[j]

 return C[i1]