高效地寻找大图中的最短路径

Question

我想找一种方法，能够实时地在一个巨大的图中找到节点之间的最短路径。这个图有成千上万的顶点和数百万条边。我知道这个问题之前有人问过，我想答案可能是使用广度优先搜索（bfs），但我更想知道有什么软件可以用来实现这个功能。比如，如果有一个现成的库（最好是有Python接口的！）可以在无向图中执行广度优先搜索，那就太完美了。

Answer 1

对于这么大的图（而且你还有性能方面的要求），你可能需要使用Boost图形库，因为它是用C++写的。它还有你需要的Python接口。

Answer 2

对于大型图形，建议使用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

根据上面的代码片段，在一个有10万个顶点和1000万个边的小世界图中，找到两个给定顶点之间的最短路径平均需要大约1.9毫秒（这是从1000次尝试中得出的平均值）。这是第一个测试案例，如果你在处理社交网络数据或其他一些已知直径相对较小的网络，这个估算是合理的。第二个测试是一个几何随机图，在一个二维平面上随机放置100万个点，如果两个点之间的距离小于0.002，就将它们连接起来，结果形成了一个大约有100万个顶点和650万个边的图。在这种情况下，计算最短路径所需的时间更长（因为路径本身也更长），但仍然相当接近实时：平均需要0.11642秒。

免责声明：我是igraph的作者之一。

编辑：网址和运行时间统计在2022年更新；代码已为Python 3重写。原始时间数据来自2010年。查看编辑历史以获取原始代码和数据。

Answer 3

python-graph

补充说明：

看到评论让我对pygraph在处理类似问题时的表现产生了好奇，所以我写了一个小程序来测试一下。以下是一个稍微小一点的问题的输出结果：

$ 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]

对于1万个节点和100万个边来说，这个表现还不错。需要注意的是，pygraph计算Dijkstra算法的方式会为每个节点生成一个字典，里面包含了相对于一个目标节点（我随便选了节点0，这个节点在图中并没有特别的地位）的所有生成树。因此，计算花了3.75分钟的结果实际上是回答了“从所有节点到目标节点的最短路径是什么？”一旦shortest_path计算完成，获取答案就只是查字典，几乎不需要时间。此外，把预先计算好的边添加到图中花费的时间也比较长，大约1.5分钟。这些时间在多次运行中是一致的。

我想说这个过程扩展性不错，但我还在等biggraph 5 6的结果，这台闲置的电脑（Athlon 64，4800 BogoMIPS每个处理器，全部在核心中）已经运行了超过15分钟。至少内存使用保持在大约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