在大图中高效地找到最短路径

新手上路,请多包涵

我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道之前有人问过这个问题,我想答案是使用广度优先搜索,但我更想知道可以使用什么软件来实现它。例如,如果它已经存在一个用于在无向图中执行 bfs 的库(带有 python 绑定!),那将是完全完美的。

原文由 Björn Lindqvist 发布,翻译遵循 CC BY-SA 4.0 许可协议

阅读 674
2 个回答

蟒蛇图

添加:

这些评论让我很好奇pygraph的性能如何针对OP的顺序问题,所以我做了一个玩具程序来了解一下。这是该问题的较小版本的输出:

 $ python2.6 biggraph.py 4 6
biggraph generate 10000 nodes     00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:05
biggraph Dijkstra                 00:01:32
biggraph shortest_path done       00:04:15
step: 1915 2
step: 0 1
biggraph walk done                00:04:15
path: [9999, 1915, 0]

对于 10k 节点和 1M 边缘来说还不错。重要的是要注意,pygraph 计算 Dijkstra 的方式会生成一个字典,其中包含每个节点相对于一个目标的所有生成树(它是任意节点 0,并且在图中没有特权位置)。因此,这个计算耗时3.75分钟的解,实际上给出了“从所有节点到目标的最短路径是什么?”的答案。确实一旦 shortest_path 完成,走答案只是字典查找,基本上没有时间。还值得注意的是,将预先计算的边添加到图中的成本相当高,大约需要 1.5 分钟。这些时间在多次运行中是一致的。

我想说这个过程可以很好地扩展,但我仍在等待 biggraph 5 6 已经运行超过一刻钟。至少内存使用稳定在0.5GB左右。结果是:

 biggraph generate 100000 nodes    00:00:00
biggraph generate 1000000 edges   00:00:00
biggraph add edges                00:00:07
biggraph Dijkstra                 00:01:27
biggraph shortest_path done       00:23:44
step: 48437 4
step: 66200 3
step: 83824 2
step: 0 1
biggraph walk done                00:23:44
path: [99999, 48437, 66200, 83824, 0]

这是一个很长的时间,但它也是一个繁重的计算(我真的希望我已经腌制了结果)。这是好奇的代码:

 #!/usr/bin/python

import pygraph.classes.graph
import pygraph.algorithms
import pygraph.algorithms.minmax
import time
import random
import sys

if len(sys.argv) != 3:
    print ('usage %s: node_exponent edge_exponent' % sys.argv[0])
    sys.exit(1)

nnodes = 10**int(sys.argv[1])
nedges = 10**int(sys.argv[2])

start_time = time.clock()
def timestamp(s):
    t = time.gmtime(time.clock() - start_time)
    print 'biggraph', s.ljust(24), time.strftime('%H:%M:%S', t)

timestamp('generate %d nodes' % nnodes)
bg = pygraph.classes.graph.graph()
bg.add_nodes(xrange(nnodes))

timestamp('generate %d edges' % nedges)
edges = set()
while len(edges) < nedges:
    left, right = random.randrange(nnodes), random.randrange(nnodes)
    if left == right:
        continue
    elif left > right:
        left, right = right, left
    edges.add((left, right))

timestamp('add edges')
for edge in edges:
    bg.add_edge(edge)

timestamp("Dijkstra")
target = 0
span, dist = pygraph.algorithms.minmax.shortest_path(bg, target)
timestamp('shortest_path done')

# the paths from any node to target is in dict span, let's
# pick any arbitrary node (the last one) and walk to the
# target from there, the associated distance will decrease
# monotonically
lastnode = nnodes - 1
path = []
while lastnode != target:
    nextnode = span[lastnode]
    print 'step:', nextnode, dist[lastnode]
    assert nextnode in bg.neighbors(lastnode)
    path.append(lastnode)
    lastnode = nextnode
path.append(target)
timestamp('walk done')
print 'path:', path

原文由 msw 发布,翻译遵循 CC BY-SA 2.5 许可协议

对于大图,请尝试 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 许可协议

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题