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

Estoy usando el paquete networkx de Python.

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

Para comprobar si hay una ruta 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 – documentación de NetworkX 1.7

Usando una estructura de datos de conjunto disjunto:

Cree un conjunto de singleton para cada vértice en el gráfico, luego junte los conjuntos que contienen cada uno de los pares de vértices para cada borde del gráfico.

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

Vea la página de wikipedia en la estructura de datos del conjunto disjunto.

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

Utilizar

 shortest_path(G, source, target) 

o uno de los métodos de ruta más corta. Manténgase alejado de los métodos que devuelven rutas entre todos los nodos, sin embargo, si simplemente tiene dos nodos específicos para probar la conectividad.

  • dijkstra_path(G, source, target)

    Devuelve la ruta más corta desde el origen al destino en un gráfico ponderado G.