我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道之前有人问过这个问题,我想答案是使用广度优先搜索,但我更想知道可以使用什么软件来实现它。例如,如果它已经存在一个用于在无向图中执行 bfs 的库(带有 python 绑定!),那将是完全完美的。
原文由 Björn Lindqvist 发布,翻译遵循 CC BY-SA 4.0 许可协议
我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道之前有人问过这个问题,我想答案是使用广度优先搜索,但我更想知道可以使用什么软件来实现它。例如,如果它已经存在一个用于在无向图中执行 bfs 的库(带有 python 绑定!),那将是完全完美的。
原文由 Björn Lindqvist 发布,翻译遵循 CC BY-SA 4.0 许可协议
对于大图,请尝试 igraph 的 Python 接口。它的核心是用C实现的,因此它可以相对轻松地处理具有数百万个顶点和边的图。它包含 BFS 实现(以及其他算法),还包括 Dijkstra 算法和用于加权图的 Bellman-Ford 算法。
至于“实时性”,我也做了一些快速测试:
from igraph import *
from random import randint
import time
def test_shortest_path(graph, tries=1000):
t1 = time.time()
for _ in range(tries):
v1 = randint(0, graph.vcount()-1)
v2 = randint(0, graph.vcount()-1)
sp = graph.get_shortest_paths(v1, v2)
t2 = time.time()
return (t2-t1)/tries
>>> print(test_shortest_path(Graph.Barabasi(100000, 100)))
0.00194978928565979
>>> print(test_shortest_path(Graph.GRG(1000000, 0.002)))
0.11642193007469177
根据上面的代码片段,在具有 100K 个顶点和 10M 个边 (10M = 100K * 100) 的小世界图中找到两个给定顶点之间的最短路径平均需要大约 1.9 毫秒(从 1000 次尝试中取平均值)。这是第一个测试用例,如果您正在使用社交网络数据或已知直径小于网络规模的其他网络,这是一个合理的估计。第二个测试是一个几何随机图,其中 100 万个点随机放置在 2D 平面上,如果两个点的距离小于 0.002,则连接两个点,从而产生一个具有大约 1M 个顶点和 6.5M 个边的图。在这种情况下,最短路径计算需要更长的时间(因为路径本身更长),但它仍然非常接近实时:平均 0.11642 秒。
免责声明:我是 igraph 的作者之一。
_编辑_:URL 和运行时统计信息在 2022 年更新;为 Python 3 重新编写的代码。最初的时间是从 2010 年开始的。检查原始代码和数据的编辑历史。
原文由 Tamás 发布,翻译遵循 CC BY-SA 4.0 许可协议
2 回答5.2k 阅读✓ 已解决
2 回答1.1k 阅读✓ 已解决
4 回答1.4k 阅读✓ 已解决
3 回答1.3k 阅读✓ 已解决
3 回答1.3k 阅读✓ 已解决
2 回答865 阅读✓ 已解决
1 回答1.7k 阅读✓ 已解决
蟒蛇图
添加:
这些评论让我很好奇pygraph的性能如何针对OP的顺序问题,所以我做了一个玩具程序来了解一下。这是该问题的较小版本的输出:
对于 10k 节点和 1M 边缘来说还不错。重要的是要注意,pygraph 计算 Dijkstra 的方式会生成一个字典,其中包含每个节点相对于一个目标的所有生成树(它是任意节点 0,并且在图中没有特权位置)。因此,这个计算耗时3.75分钟的解,实际上给出了“从所有节点到目标的最短路径是什么?”的答案。确实一旦
shortest_path
完成,走答案只是字典查找,基本上没有时间。还值得注意的是,将预先计算的边添加到图中的成本相当高,大约需要 1.5 分钟。这些时间在多次运行中是一致的。我想说这个过程可以很好地扩展,但我仍在等待
biggraph 5 6
在 已经运行超过一刻钟。至少内存使用稳定在0.5GB左右。结果是:这是一个很长的时间,但它也是一个繁重的计算(我真的希望我已经腌制了结果)。这是好奇的代码: