使用NetworkX "路径“函数,可以在图G中找到所有对最短路径。现在,假设图G是如此大,比如说包含10万个节点,我只想为节点的子集找到最短路径,比如1000个随机绘制的节点。
使用NetworkX的“NetworkX”函数,我可以循环遍历节点的子集,并找到我要查找的内容。但是,这样做似乎并不有效,因为我将调用函数n时间(假设子集的长度为n),到目前为止被调查的信息将被丢弃。我读了多篇文章,提到all_pairs函数更适合搜索所有对之间的路径,而不是在循环中使用单个源对目标函数。是否有一种方法可以在NetworkX中提供节点子集作为输入?或者说,下一步的最佳方法是什么?
这个问题是这未回答问题的重复。
发布于 2021-12-17 09:32:09
特别是对于networkx的all_pairs_dijkstra_path,您不会因为调用n times single_source_dijkstra_path而失去任何性能。如果您查看all_pairs_dijkstra_path的实现,这将变得非常清楚。
def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
""" < docs """
path = single_source_dijkstra_path
# TODO This can be trivially parallelized.
for n in G:
yield (n, path(G, n, cutoff=cutoff, weight=weight))如果你需要更多的信息,你应该对你的情况更加具体:
但也许更重要的是,您是否只是在1000个节点上尝试过循环呢?(或从30开始并检查运行时)。许多事情将取决于您的用例和您想要计算或近似的内容。
https://stackoverflow.com/questions/70368402
复制相似问题