我正在寻找一种方法来实时找到巨大图中节点之间的最短路径。它有数十万个顶点和数百万条边。我知道以前有人问过这个问题，我想答案是使用广度优先搜索，但我更感兴趣的是知道你可以用什么软件来实现它。例如，如果它已经存在用于在无向图中执行 bfs 的库（带有 python 绑定！），那将是完全完美的。
问问题
24107 次
7 回答
19
添加：
这些评论让我很好奇 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的闲置计算机（Athlon 64，每个处理器 4800 BogoMIPS ，全部在核心）。至少内存使用稳定在 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
于 2010-06-14T15:54:48.700 回答
11
对于大图，请尝试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 xrange(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.010035698396
>>> print test_shortest_path(Graph.GRG(1000000, 0.002))
0.413572219742
根据上面的代码片段，在具有 100K 顶点和 10M 边（10M = 100K * 100）的小世界图中找到两个给定顶点之间的最短路径平均需要大约 0.01003 秒（平均从 1000 次尝试）。这是第一个测试用例，如果您使用的是社交网络数据或其他已知直径与网络大小相比较小的网络，这是一个合理的估计。第二个测试是一个几何随机图，其中 100 万个点在 2D 平面上随机下降，如果两个点的距离小于 0.002，则连接两个点，得到一个大约 1M 顶点和 6.5M 边的图。在这种情况下，最短路径计算需要更长的时间（因为路径本身更长），但它仍然非常接近实时：平均 0.41357 秒。
免责声明：我是igraph的作者之一。
于 2010-06-14T20:53:40.790 回答
3
对于那么大的图（并且具有您的性能限制），您可能需要Boost 图形库，因为它是用 C++ 编写的。它具有您正在寻找的Python 绑定。
于 2010-06-14T16:26:21.047 回答
3
好吧，这取决于您将多少元数据附加到节点和边缘。如果相对较小，那么该图的大小将适合内存，因此我推荐优秀的 NetworkX 包（特别是参见http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html），它是纯粹的Python。
对于可以处理数百万个节点、大型元数据、事务、磁盘存储等的更强大的解决方案，我对 neo4j ( http://www.neo4j.org/ ) 非常满意。它是用 Java 编写的，但具有 Python 绑定或可以作为 REST 服务器运行。遍历它有点小技巧，但还不错。
于 2010-06-14T20:37:41.443 回答
1
无向图中的 BFS 只有大约 25 行代码。你不需要图书馆。查看Wikipedia 文章中的示例代码。
于 2010-06-14T15:54:27.297 回答
0
根据您拥有的附加信息类型，A* 可能非常有效。特别是，如果给定一个节点，您可以计算从该节点到目标的成本估计，A* 是最有效的。
于 2010-06-15T02:06:49.120 回答
0
存储在neo4j
它包括 Dijkstra、A*、“最短路径”算法。
于 2013-02-15T06:22:53.877 回答