我需要找到有向图中每对节点之间的所有最短路径。我正在做的是:
for i in A.nodes()
for y in A.nodes()
paths = nx.all_shortest_paths(G,i,y)
但我猜这很慢,因为在图中有很多节点无论如何都与 i 没有连接。 有没有办法优化这个过程?我已经在注意不可能连接到其他节点的节点不会在 A 中结束。
请您参考如下方法:
内置命令: single_source_shortest_path_length(G, source) 为您提供源和每个可达节点之间的最短路径。
import networkx as nx
G=nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (3,4), (1,5), (2,5), (6,7)]) #6,7 not reachable from 1
nx.single_source_shortest_path(G,1)
>{1: [1], 2: [1, 2], 3: [1, 2, 3], 4: [1, 2, 3, 4], 5: [1, 5]}
问题标题表明您只想知道可达节点而不是路径。在这种情况下,请使用深度优先或广度优先搜索。文档是 here .例如:dfs_postorder_nodes(G, source=None) 为可从源到达的节点提供迭代器。它们出现的特定顺序是深度优先搜索后序。
for reachable_node in nx.dfs_postorder_nodes(G,source=1):
print reachable_node
>4
>3
>5
>2
>1
