Python：如何查找图中两个节点之间是否存在路径？

Question

我正在使用Python的networkx包。

Answer 1

检查图中两个节点之间是否存在路径 -

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

有关详细信息，请参阅 has_path — NetworkX 1.7 文档

Answer 2

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

您还可以将结果用作布尔值

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

使用不相交集数据结构：

为图中的每个顶点创建一个单例集，然后合并包含图中每条边的每个顶点对的集合。

最后，如果两个顶点位于同一集合中，您就知道它们之间存在路径。

请参阅关于不相交集数据结构的 wikipedia 页面。

这比使用路径查找算法要有效得多。

Answer 4

使用

shortest_path(G, source, target)

或 最短路径方法之一。但是，如果您只有两个特定节点来测试连接性，请远离返回所有节点之间路径的方法。

Answer 5

• dijkstra_path（G，源，目标）< /代码>

  <块引用>

  返回加权图 G 中从源到目标的最短路径。