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

Question

J'utilise un package 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 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

Pour vérifier s'il y a un chemin entre deux nœuds dans un graphique -

>>> 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, veuillez vous référer Has_path - Documentation Networkx 1.7

Answer 3

Utilisation d'une structure de données définie disjointe:

Créez un ensemble de singleton pour chaque sommet du graphique, puis Union les ensembles contenant chacune des paires de sommets pour chaque bord du graphique.

Enfin, vous savez qu'un chemin existe entre deux sommets s'ils sont dans le même ensemble.

Voir le Wikipédia Page sur la structure de données de définition disjointe.

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

Answer 4

Utilisation

shortest_path(G, source, target)

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

Answer 5

• dijkstra_path(G, source, target)

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