python - 有效地找到大图中的最短路径

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

最佳答案

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]

对于10公里节点和1米边缘来说还不错。重要的是要注意，Pygraph计算dijkstra的方式会为每个节点生成一个相对于一个目标的所有生成树的字典（它是任意节点0，并且在图中没有特权位置）。因此，花了3.75分钟计算的解决方案实际上给出了“从所有节点到目标的最短路径是什么？”确实，一旦完成了任务，浏览答案只需查字典，基本上不需要花时间。同样值得注意的是，在约1.5分钟的时间内，将预先计算的边添加到图中相当昂贵。这些计时在多次运行中是一致的。
我想说这个过程扩展得很好，但是我仍然在一台闲置的计算机上等待shortest_path（Athlon 64，4800BogoMIPS每台处理器，全部在内核中），这台计算机已经运行了四分之一个多小时了。至少内存使用稳定在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

关于python - 有效地找到大图中的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3038661/