查找 NetworkX 中所有节点对之间的所有最短路径
Find all shortest paths between all pairs of nodes in NetworkX
我正在尝试获取无向未加权图中所有节点对之间的所有最短路径。我目前正在使用 nx.all_pairs_shortest_path()
,但我不明白为什么每对节点只有 returns 一条最短路径。我的图中有循环,因此某些节点之间应该存在多条最短路径。有什么建议吗?
迭代图中的所有节点:
results = []
for n1 in G.nodes():
for n2 in G.nodes():
shortest_path = nx.single_source_dijkstra(G, source=n1, target=n2, weight=f)
results.append(shortest_path)
我可能来晚了,但我刚遇到同样的问题,这是我的解决方案:
def all_shortest_paths(G):
a = list(nx.all_pairs_shortest_path(G))
all_sp_list = []
for n in range(len(G.nodes)):
a1 = a[n][1]
for k,v in a1.items():
all_sp_list.append(len(v))
return all_sp_list
我尝试的所有其他方法都变得非常非常慢,因为我的图表有一堆节点,所以这是我最快的解决方案。
我自己偶然发现了这个问题,并找到了她来寻求解决方案。不幸的是,networkx 没有计算每对节点的所有最短路径的功能。此外,Igor Michetti 的回答根本没有给出我想要的,但它可能是可以调整的。
math_noob 的回答很好,因为它足够接近我想出的解决方案,但问题是它太慢了。
def single_source_shortest_paths(graph,source):
shortest_paths_dict = {}
for node in graph:
shortest_paths_dict[node] = list(nx.all_shortest_paths(graph,source,node))
return shortest_paths_dict
def all_shortest_paths(graph):
for source in graph:
yield source, single_source_shortest_paths(source)
所以我回到了 networkx 文档并尝试最后一次找到一个是否有任何我可以使用的功能。但是有 none 所以我决定我会实施它 myself.So 我首先尝试通过 had 实施一切,这有点混乱,只意识到它好一点但不是那么好,所以我决定我将尝试查看源代码并发现那里有一个圣杯,即 nx.predecessor
函数。
此函数仅在图和源节点上调用,因此它不依赖于目标节点,并且它是完成大部分艰苦工作的节点。所以我只是重新创建了函数 single_source_shortest_paths
,但是每个源节点只调用一次 nx.predecessor
,然后执行与 all_shortest_path
相同的操作,只包括使用正确的参数调用另一个函数。
def single_source_shortest_paths_pred(graph,source):
shortest_paths_dict = {}
pred = nx.predecessor(graph,source)
for node in graph:
shortest_paths_dict[node] = list(nx.algorithms.shortest_paths.generic._build_paths_from_predecessors([source], node, pred))
return shortest_paths_dict
就时间而言,nx.predecessor
花费了大部分时间来执行,因此第二个函数快了大约 n 倍,其中 n 是图中的节点数
我正在尝试获取无向未加权图中所有节点对之间的所有最短路径。我目前正在使用 nx.all_pairs_shortest_path()
,但我不明白为什么每对节点只有 returns 一条最短路径。我的图中有循环,因此某些节点之间应该存在多条最短路径。有什么建议吗?
迭代图中的所有节点:
results = []
for n1 in G.nodes():
for n2 in G.nodes():
shortest_path = nx.single_source_dijkstra(G, source=n1, target=n2, weight=f)
results.append(shortest_path)
我可能来晚了,但我刚遇到同样的问题,这是我的解决方案:
def all_shortest_paths(G):
a = list(nx.all_pairs_shortest_path(G))
all_sp_list = []
for n in range(len(G.nodes)):
a1 = a[n][1]
for k,v in a1.items():
all_sp_list.append(len(v))
return all_sp_list
我尝试的所有其他方法都变得非常非常慢,因为我的图表有一堆节点,所以这是我最快的解决方案。
我自己偶然发现了这个问题,并找到了她来寻求解决方案。不幸的是,networkx 没有计算每对节点的所有最短路径的功能。此外,Igor Michetti 的回答根本没有给出我想要的,但它可能是可以调整的。
math_noob 的回答很好,因为它足够接近我想出的解决方案,但问题是它太慢了。
def single_source_shortest_paths(graph,source):
shortest_paths_dict = {}
for node in graph:
shortest_paths_dict[node] = list(nx.all_shortest_paths(graph,source,node))
return shortest_paths_dict
def all_shortest_paths(graph):
for source in graph:
yield source, single_source_shortest_paths(source)
所以我回到了 networkx 文档并尝试最后一次找到一个是否有任何我可以使用的功能。但是有 none 所以我决定我会实施它 myself.So 我首先尝试通过 had 实施一切,这有点混乱,只意识到它好一点但不是那么好,所以我决定我将尝试查看源代码并发现那里有一个圣杯,即 nx.predecessor
函数。
此函数仅在图和源节点上调用,因此它不依赖于目标节点,并且它是完成大部分艰苦工作的节点。所以我只是重新创建了函数 single_source_shortest_paths
,但是每个源节点只调用一次 nx.predecessor
,然后执行与 all_shortest_path
相同的操作,只包括使用正确的参数调用另一个函数。
def single_source_shortest_paths_pred(graph,source):
shortest_paths_dict = {}
pred = nx.predecessor(graph,source)
for node in graph:
shortest_paths_dict[node] = list(nx.algorithms.shortest_paths.generic._build_paths_from_predecessors([source], node, pred))
return shortest_paths_dict
就时间而言,nx.predecessor
花费了大部分时间来执行,因此第二个函数快了大约 n 倍,其中 n 是图中的节点数