首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >为部分节点寻找所有对最短路径

问为部分节点寻找所有对最短路径
EN

Stack Overflow用户
提问于 2021-12-15 18:07:19
回答 1查看 341关注 0票数 1

使用NetworkX "路径“函数,可以在图G中找到所有对最短路径。现在,假设图G是如此大,比如说包含10万个节点,我只想为节点的子集找到最短路径,比如1000个随机绘制的节点。

使用NetworkX的“NetworkX”函数,我可以循环遍历节点的子集,并找到我要查找的内容。但是,这样做似乎并不有效,因为我将调用函数n时间(假设子集的长度为n),到目前为止被调查的信息将被丢弃。我读了多篇文章,提到all_pairs函数更适合搜索所有对之间的路径,而不是在循环中使用单个源对目标函数。是否有一种方法可以在NetworkX中提供节点子集作为输入?或者说,下一步的最佳方法是什么?

这个问题是这未回答问题的重复。

EN

回答 1

Stack Overflow用户

发布于 2021-12-17 09:32:09

特别是对于networkx的all_pairs_dijkstra_path,您不会因为调用n times single_source_dijkstra_path而失去任何性能。如果您查看all_pairs_dijkstra_path的实现,这将变得非常清楚。

代码语言:javascript
复制
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开始并检查运行时)。许多事情将取决于您的用例和您想要计算或近似的内容。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/70368402

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档