Trouver tous les chemins entre deux nœuds de graphe

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

Ma question: Comment peut-on récupérer tous les chemins possibles à partir du nœud A pour dire le nœud G ou même tous les chemins possibles du nœud A et retour vers le nœud A?

Trouver tous les chemins possibles est un problème difficile, car il existe un nombre exponentiel de chemins simples. Même trouver le kème plus court chemin [ou le plus long chemin] est NP-Hard .

Une solution possible pour trouver tous les chemins [ou tous les chemins jusqu’à une certaine longueur] de s à t est BFS , sans conserver un ensemble visited , ou pour la version pondérée – vous pouvez utiliser une recherche de coût uniforme

Notez que même dans chaque graphe qui a des cycles [ce n’est pas un DAG ] il peut y avoir un nombre infini de chemins entre s et t .

J’ai implémenté une version où il est possible de trouver tous les chemins possibles d’un nœud à l’autre, mais il ne compte aucun «cycle» possible (le graphique que j’utilise est cyclique). Donc, fondamentalement, aucun nœud n’apparaîtra deux fois dans le même chemin. Et si le graphique était acyclique, alors je suppose que vous pourriez dire qu’il semble trouver tous les chemins possibles entre les deux nœuds. Il semble fonctionner correctement, et pour la taille de mon graphique de ~ 150, il fonctionne presque instantanément sur ma machine, bien que je sois sûr que le temps d’exécution doit être quelque chose comme exponentiel graphe devient plus grand.

Voici un code Java qui montre ce que j’ai implémenté. Je suis sûr qu’il doit y avoir des moyens plus efficaces ou élégants de le faire aussi.

 Stack connectionPath = new Stack(); List connectionPaths = new ArrayList<>(); // Push to connectionsPath the object that would be passed as the parameter 'node' into the method below void findAllPaths(Object node, Object targetNode) { for (Object nextNode : nextNodes(node)) { if (nextNode.equals(targetNode)) { Stack temp = new Stack(); for (Object node1 : connectionPath) temp.add(node1); connectionPaths.add(temp); } else if (!connectionPath.contains(nextNode)) { connectionPath.push(nextNode); findAllPaths(nextNode, targetNode); connectionPath.pop(); } } } 

Je vais vous donner une version (un peu petite) (bien que compréhensible, je pense) d’une preuve scientifique que vous ne pouvez pas le faire dans un délai raisonnable.

Ce que je vais prouver est que la complexité temporelle pour énumérer tous les chemins simples entre deux nœuds sélectionnés et distincts (dis, s et t ) dans un graphe arbitraire G n’est pas polynomiale. Notez que, comme nous ne nous préoccupons que de la quantité de chemins entre ces nœuds, les coûts marginaux sont sans importance.

Assurez-vous que si le graphique a des propriétés bien sélectionnées, cela peut être facile. Je considère le cas général cependant.


Supposons que nous ayons un algorithme polynomial qui répertorie tous les chemins simples entre s et t .

Si G est connecté, la liste est vide. Si G n’est pas et que s et t sont dans des composants différents, il est vraiment facile de lister tous les chemins entre eux, car il n’y en a pas! S’ils sont dans le même composant, on peut prétendre que le graphique entier ne comprend que ce composant. Supposons donc que G soit effectivement connecté.

Le nombre de chemins listés doit alors être polynomial, sinon l’algorithme ne pourrait pas les renvoyer tous. S’il les énumère tous, il doit me donner le plus long, donc il est là. Ayant la liste des chemins, une procédure simple peut être appliquée pour indiquer quel est ce chemin le plus long.

Nous pouvons montrer (bien que je ne puisse pas penser à une manière cohérente de le dire) que ce chemin le plus long doit traverser tous les sumts de G Ainsi, nous venons de trouver un chemin hamiltonien avec une procédure polynomiale! Mais c’est un problème NP-difficile bien connu.

Nous pouvons alors conclure que cet algorithme polynomial que nous pensions avoir existait très peu , à moins que P = NP .

Voici un algorithme permettant de trouver et d’imprimer tous les chemins entre s et t en utilisant la modification de DFS. La programmation dynamic 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 

Vous ne le voulez généralement pas, car il y en a un nombre exponentiel dans les graphiques non sortingviaux; Si vous voulez vraiment obtenir tous les chemins (simples), ou tous les (simples) cycles, il vous suffit d’en trouver un (en parcourant le graphique), puis de revenir en arrière vers un autre.

Je pense que ce que vous voulez, c’est une forme de l’algorithme de Ford – Fulkerson basé sur BFS. Il est utilisé pour calculer le débit maximal d’un réseau, en trouvant tous les chemins d’augmentation entre deux nœuds.

http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

find_paths [s, t, d, k]

Cette question est maintenant un peu ancienne … mais je jetterai mon chapeau sur le ring.

Je trouve personnellement un algorithme de la forme find_paths[s, t, d, k] utile, où:

  • s est le noeud de départ
  • t est le noeud cible
  • d est la profondeur maximale à rechercher
  • k est le nombre de chemins à trouver

L’utilisation de l’infini de votre langage de programmation pour d et k vous donnera tous les chemins§.

§ évidemment, si vous utilisez un graphe orienté et que vous voulez tous les chemins non orientés entre s et t vous devrez exécuter cette opération dans les deux sens:

 find_paths[s, t, d, k]  find_paths[t, s, d, k] 

Fonction d’assistance

Personnellement, j’aime la récursivité, même si cela peut parfois être difficile, de toute façon, définissons d’abord notre fonction d’assistance:

 def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found) current_path.append(current) if current_depth > max_depth: return if current == goal: if len(paths_found) <= number_of_paths_to_find: paths_found.append(copy(current_path)) current_path.pop() return else: for successor in graph[current]: self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found) current_path.pop() 

Fonction principale

Avec ça, la fonction principale est sortingviale:

 def find_paths[s, t, d, k]: paths_found = [] # PASSING THIS BY REFERENCE find_paths_recursion(s, t, 0, d, k, [], paths_found) 

Tout d'abord, remarquons quelques choses:

  • le pseudo-code ci-dessus est un mélange de langues - mais ressemble beaucoup à python (puisque je ne faisais que le coder). Un copier-coller ssortingct ne fonctionnera pas.
  • [] est une liste non initialisée, remplacez-la par l’équivalent de votre langage de programmation de choix
  • paths_found est passé par référence . Il est clair que la fonction de récursivité ne renvoie rien. Manipulez ceci correctement.
  • ici le graph suppose une forme de structure hashed . Il existe une multitude de façons de mettre en œuvre un graphique. Dans les deux cas, graph[vertex] vous fournit une liste de sumts adjacents dans un graphe orienté - ajustez en conséquence.
  • cela suppose que vous ayez prétraité pour supprimer les "boucles" (boucles automatiques), les cycles et les multi-bords

Si vous tenez à ordonner vos chemins du plus court chemin au plus long chemin, il serait préférable d’utiliser un algorithme A * ou Dijkstra modifié . Avec une légère modification, l’algorithme renverra autant de chemins possibles que vous le souhaitez dans l’ordre du plus court chemin. Donc, si ce que vous voulez vraiment, ce sont tous les chemins possibles ordonnés du plus court au plus long, alors c’est la voie à suivre.

Si vous voulez une implémentation basée sur A * capable de renvoyer tous les chemins ordonnés du plus court au plus long, voici ce que vous accomplirez. Il a plusieurs avantages. Tout d’abord, il est efficace pour le sorting du plus court au plus long. En outre, il calcule chaque chemin supplémentaire uniquement lorsque cela est nécessaire, donc si vous vous arrêtez tôt car vous n’avez pas besoin de chaque chemin, vous gagnez du temps de traitement. Il réutilise également les données pour les chemins suivants chaque fois qu’il calcule le chemin suivant pour qu’il soit plus efficace. Enfin, si vous trouvez le chemin souhaité, vous pouvez interrompre rapidement l’économie de temps de calcul. Globalement, cela devrait être l’algorithme le plus efficace si vous tenez au sorting par longueur de chemin.

 import java.util.*; public class AstarSearch { private final Map> adjacency; private final int destination; private final NavigableSet pending = new TreeSet<>(); public AstarSearch(Map> adjacency, int source, int destination) { this.adjacency = adjacency; this.destination = destination; this.pending.add(new Step(source, null, 0)); } public List nextShortestPath() { Step current = this.pending.pollFirst(); while( current != null) { if( current.getId() == this.destination ) return current.generatePath(); for (Neighbor neighbor : this.adjacency.get(current.id)) { if(!current.seen(neighbor.getId())) { final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination)); this.pending.add(nextStep); } } current = this.pending.pollFirst(); } return null; } protected int predictCost(int source, int destination) { return 0; //Behaves identical to Dijkstra's algorithm, override to make it A* } private static class Step implements Comparable { final int id; final Step parent; final int cost; public Step(int id, Step parent, int cost) { this.id = id; this.parent = parent; this.cost = cost; } public int getId() { return id; } public Step getParent() { return parent; } public int getCost() { return cost; } public boolean seen(int node) { if(this.id == node) return true; else if(parent == null) return false; else return this.parent.seen(node); } public List generatePath() { final List path; if(this.parent != null) path = this.parent.generatePath(); else path = new ArrayList<>(); path.add(this.id); return path; } @Override public int compareTo(Step step) { if(step == null) return 1; if( this.cost != step.cost) return Integer.compare(this.cost, step.cost); if( this.id != step.id ) return Integer.compare(this.id, step.id); if( this.parent != null ) this.parent.compareTo(step.parent); if(step.parent == null) return 0; return -1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Step step = (Step) o; return id == step.id && cost == step.cost && Objects.equals(parent, step.parent); } @Override public int hashCode() { return Objects.hash(id, parent, cost); } } /******************************************************* * Everything below here just sets up your adjacency * * It will just be helpful for you to be able to test * * It isnt part of the actual A* search algorithm * ********************************************************/ private static class Neighbor { final int id; final int cost; public Neighbor(int id, int cost) { this.id = id; this.cost = cost; } public int getId() { return id; } public int getCost() { return cost; } } public static void main(String[] args) { final Map> adjacency = createAdjacency(); final AstarSearch search = new AstarSearch(adjacency, 1, 4); System.out.println("printing all paths from shortest to longest..."); List path = search.nextShortestPath(); while(path != null) { System.out.println(path); path = search.nextShortestPath(); } } private static Map> createAdjacency() { final Map> adjacency = new HashMap<>(); //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. addAdjacency(adjacency, 1,2,1,5,1); //{1 | 2,5} addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5} addAdjacency(adjacency, 3,2,1,5,1); //{3 | 2,5} addAdjacency(adjacency, 4,2,1); //{4 | 2} addAdjacency(adjacency, 5,1,1,2,1,3,1); //{5 | 1,2,3} return Collections.unmodifiableMap(adjacency); } private static void addAdjacency(Map> adjacency, int source, Integer... dests) { if( dests.length % 2 != 0) throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal"); final Set destinations = new HashSet<>(); for(int i = 0; i < dests.length; i+=2) destinations.add(new Neighbor(dests[i], dests[i+1])); adjacency.put(source, Collections.unmodifiableSet(destinations)); } } 

La sortie du code ci-dessus est la suivante:

 [1, 2, 4] [1, 5, 2, 4] [1, 5, 3, 2, 4] 

Notez que chaque fois que vous appelez nextShortestPath() il génère le prochain plus court chemin à votre demande. Il ne calcule que les étapes supplémentaires nécessaires et ne traverse pas deux anciens chemins. De plus, si vous décidez que vous n'avez pas besoin de tous les chemins et que vous finissez tôt, vous avez économisé un temps de calcul considérable. Vous ne calculez que le nombre de chemins dont vous avez besoin et pas plus.

Enfin, il convient de noter que les algorithmes A * et Dijkstra ont quelques limitations mineures, bien que je ne pense pas que cela vous affecterait. À savoir, cela ne fonctionnera pas directement sur un graphique qui a des poids négatifs.

Voici un lien vers JDoodle où vous pouvez exécuter le code vous-même dans le navigateur et le voir fonctionner. Vous pouvez également modifier le graphique pour montrer qu'il fonctionne également sur d'autres graphiques: http://jdoodle.com/a/ukx

Je suppose que vous voulez trouver des chemins “simples” (un chemin est simple si aucun nœud n’y figure plus d’une fois, sauf peut-être le premier et le dernier).

Comme le problème est NP-difficile, vous pouvez faire une variante de la recherche en profondeur.

Fondamentalement, générez tous les chemins possibles à partir de A et vérifiez s’ils se retrouvent dans G.

Il y a un bon article qui peut répondre à votre question / seulement il imprime les chemins au lieu de les collecter /. Veuillez noter que vous pouvez tester les exemples C ++ / Python dans l’EDI en ligne.

http://www.geeksforgeeks.org/find-paths-given-source-destination/