Python: Comment trouver si un chemin existe entre 2 nœuds dans un graphique?

Question

J'utilise le paquet networkx de Python.

Answer 1

>>> import networkx as nx 
>>> G=nx.empty_graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> G.add_edge(4,5) 
>>> nx.path.bidirectional_dijkstra(G,1,2) 
(1, [1, 2]) 
>>> nx.path.bidirectional_dijkstra(G,1,3) 
(2, [1, 2, 3]) 
>>> nx.path.bidirectional_dijkstra(G,1,4) 
False 
>>> nx.path.bidirectional_dijkstra(G,1,5) 
False 
>>> 

Vous pouvez également utiliser le résultat comme une valeur booléenne

>>> if nx.path.bidirectional_dijkstra(G,1,2): print "path exists" 
... 
path exists 
>>> if nx.path.bidirectional_dijkstra(G,1,4): print "path exists" 
... 
>>> 

Answer 2

• dijkstra_path(G, source, target)

  Renvoie le chemin le plus court de source vers la cible dans un graphe pondéré G.

Answer 3

Utilisez

shortest_path(G, source, target) 

ou l'une des méthodes Shortest Path. Restez à l'écart des méthodes qui renvoient des chemins entre tous les nœuds, mais si vous avez simplement deux nœuds spécifiques à tester pour la connectivité.

Answer 4

En utilisant une structure de données de jeu disjoints:

Créer un singleton pour chaque sommet du graphe, puis les syndicats ensembles contenant chacun des deux sommets pour chaque bord dans le graphique. Enfin, vous savez qu'un chemin existe entre deux sommets s'ils sont dans le même ensemble.

Voir la page wikipedia sur la structure de données des ensembles disjoints.

Ceci est beaucoup plus efficace que d'utiliser un algorithme de recherche de chemin.

Answer 5

Pour vérifier s'il y a un chemin entre deux noeuds dans un graphe -

>>> import networkx as nx 
>>> G=nx.Graph() 
>>> G.add_edge(1,2) 
>>> G.add_edge(2,3) 
>>> nx.has_path(G,1,3) 
True 
>>> G.add_edge(4,5) 
>>> nx.has_path(G,1,5) 
False 

Pour plus d'informations, s'il vous plaît se référer has_path — NetworkX 1.7 documentation