Algorithme efficace pour trouver tous les chemins entre deux nœuds
Je suis en train de travailler sur un récursif DFS pour récupérer tous les chemins entre deux nœuds dans un non-orienté et non pondérées graphique pour l'instant. Il prend le début et la fin de nœud, et DFS sur le nœud et de ses nœuds adjacents, de manière récursive, tout en économisant les chemins.
Je me demandais si il existe un moyen plus efficace de trouver tous les chemins?
Si vous voulez trouver tous les chemins, alors vous avez à marcher à travers eux tous... voulez-vous simplement à trouver le nombre de chemins? Alors il y a peut être des méthodes plus rapides.
Si vous êtes intéressé seulement par le nombre, cependant, il pourrait y avoir des algorithmes plus efficaces
Je veux faire un peu de travail sur les nœuds sur chacun de ces chemins; donc j'ai besoin de trouver tous les chemins et les enregistrer, et pas seulement leur nombre.
Si vous êtes intéressé seulement par le nombre, cependant, il pourrait y avoir des algorithmes plus efficaces
Je veux faire un peu de travail sur les nœuds sur chacun de ces chemins; donc j'ai besoin de trouver tous les chemins et les enregistrer, et pas seulement leur nombre.
OriginalL'auteur Phat | 2012-12-30
Vous devez vous connecter pour publier un commentaire.
Il y a nombre exponentiel de chemins simples, et DFS est essentiellement la création de tous 0 de sorte que votre approche est correcte, même si de temps (mais c'est une partie du problème lui-même, pas de l'algorithme).
Vous pourriez être en mesure d'optimiser un peu par élimination de l'noeuds d'un graphe qui ne conduisent pas à la cible, si de tels nœuds existent de manière parage infructueuse recherches avant de calculer.
Être conscient que si le graphe contient des cycles - il pourrait y avoir nombre infini de chemins (bien que nombre fini de simple chemins d'accès). Notez que pour éviter une boucle infinie et d'obtenir tous les chemins simples, votre DFS aurez besoin de maintenir un
visited
ensemble, qui est modifié par un chemin (une fois "à la découverte" d'un nœud de l'insérer à l'ensemble, et une fois qu'il est sorti de la pile, retirez-la de l'ensemble).L'algorithme est
O(n!)
, envisager une clique, à la source, vous avez n-1 nœuds à visiter, plus tard, n-2, n-3, ... jusqu'à ce que vous atteignez la cible. Cela aurait entraîné seul dansO((n-1)!)
, mais vous avez besoin d'un supplément den
pour traiter chaque nœud de chemin découvert.OriginalL'auteur amit
Vous pouvez adapter l'algorithme de Dijkstra, voir aussi Un Algorithme Récursif de Trouver tous les Chemins Entre Deux Nœuds
OriginalL'auteur user1929959