题
我正在使用Python的NetworkX软件包。
解决方案
>>> 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"
...
>>>
其他提示
检查图中的两个节点之间是否有路径 -
>>> 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 - 网络X 1.7文档
使用脱节集数据结构:
为图中的每个顶点创建一个单例集,然后将包含图表中每个边缘的每个顶点的集合组合在一起。
最后,您知道,如果两个顶点在同一组中,则存在一条路径。
看到 维基百科 在“脱节设置数据结构”上的页面。
这比使用路径查找算法要高得多。
利用
shortest_path(G, source, target)
或最短路径方法之一。请务必清除所有节点之间返回路径的方法,但是,如果您只有两个特定节点可以测试连接性。
dijkstra_path(G, source, target)
在加权图G中返回从源到目标的最短路径。
不隶属于 StackOverflow