Python: ¿Cómo encontrar si existe una ruta entre 2 nodos en un gráfico?

Question

Estoy usando el paquete de red 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 
>>> 

También puede utilizar el resultado como un valor booleano

>>> 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)

  devuelve la ruta más corta desde el origen al destino en un grafo ponderado G.

Answer 3

Uso

shortest_path(G, source, target) 

o uno de los métodos camino más corto. Sin embargo, manténgase alejado de los métodos que devuelven las rutas entre todos los nodos si solo tiene dos nodos específicos para probar la conectividad.

Answer 4

Uso de una estructura de datos conjunto disjuntos:

Crear un conjunto unitario para cada vértice en el gráfico, entonces Unión los conjuntos que contienen cada uno del par de vértices por cada borde en el gráfico.

Finalmente, sabes que existe una ruta entre dos vértices si están en el mismo conjunto.

Consulte la página wikipedia en la estructura de datos de conjunto disjuntos.

Esto es mucho más eficiente que usar un algoritmo de búsqueda de ruta.

Answer 5

Para comprobar si existe un camino entre dos nodos en un gráfico -

>>> 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 

Para obtener más información, consulte has_path — NetworkX 1.7 documentation