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

Question

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

pythongraphshortest-pathdijkstrabreadth-first-search

16

我希望找到一种实时查找巨大图中节点之间最短路径的方法。该图有数十万个顶点和数百万条边。我知道这个问题以前已经被问过了，我猜答案是使用广度优先搜索算法，但我更想知道可以使用哪些软件来实现它。比如说，如果已经存在一个库（带有Python绑定！）用于在无向图中执行广度优先搜索算法，那将会非常完美。

- Björn Lindqvist

3

如果你的图中每条边的权重相同，广度优先搜索（BFS）才能正常运行。除此之外，相比于BFS，使用Dijkstra算法、一致代价搜索（Uniform Cost Search）或A*算法，通常可以获得更好的性能表现。 - Brad Larsen

你的图是显式地存储在核心内存中吗？还是使用归纳描述来处理图形？ - Brad Larsen

我猜我应该提到这个。:/ 数据存储在数据库中。但是我正在考虑将图形存储在某种基于磁盘的数据结构中，因为它太大了，无法完全读入内存。当然，这意味着需要整个图形都在内存中运行的软件将无法使用。 - Björn Lindqvist

7个回答

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 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万条边（10M = 100K * 100）的小世界图中寻找两个给定顶点之间的最短路径平均需要1.9毫秒（从1000次尝试中取平均值）。如果你正在处理社交网络数据或其他知道直径相对于网络大小很小的网络，那么这是第一个合理的测试用例。第二个测试是在二维平面上随机放置100万个点，并且连接距离小于0.002的两个点，结果得到大约1M个顶点和6.5M条边的图形随机图。在这种情况下，最短路径计算需要更长时间（因为路径本身更长），但仍然非常接近实时：平均为0.11642秒。

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

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

- Tamás

谢谢你提供指针。在Ubuntu/Debian仓库和PyPi上有它是一个加分项。你怎么知道我最近才开始用Python进行图形分析的呢？ - msw

死链：igraph -> http://igraph.sf.net/ -> https://igraph.org/redirect.html。另外，更新运行时间12年后？ - denis

好的，谢谢，已修复URL并更新了时间。 - Tamás

3

对于这么大的图（并且考虑到您的性能限制），您可能需要使用C++编写的Boost Graph Library。它具有您正在寻找的Python绑定。

- Brandon

请查看 graph-tool，它包装了 Boost Graph。 - songololo

3

嗯，这要取决于您附加到节点和边缘的元数据有多少。如果比较少，那么这种大小的图表将适合内存，并且我建议使用优秀的NetworkX包（特别是请参见http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html），它是纯Python。

对于能够处理许多百万个节点，具有大量元数据、事务、磁盘存储等更强大解决方案，我曾经用过neo4j（http://www.neo4j.org/）。它是用Java编写的，但具有Python绑定或可以作为REST服务器运行。遍历它有点棘手但不坏。

- gilesc

1

在无向图中实现BFS只需要大约25行代码，不需要使用库。请查看维基百科文章中的示例代码。

- dmazzoni

0

根据您拥有的额外信息类型，A*算法可能非常高效。特别是，如果给定一个节点，您可以计算从该节点到目标的成本估计值，那么A*算法将是最优高效的。

- ggambetta

0

存储在neo4j中

它包括Dijkstra、A*和“最短路径”算法。

- Evgenii

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- msw · Accepted Answer

Python图形

添加：

评论让我对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]

对于1万个节点和100万条边来说，效果还不错。需要注意的是，通过pygraph计算Dijkstra的方式会相对于一个目标节点（这里是任意选定的节点0，在图中没有特殊地位）得到所有节点的生成树字典。因此，花费3.75分钟计算出的解决方案实际上回答了“所有节点到目标节点的最短路径是什么？”的问题。实际上，一旦完成shortest_path，查找答案只需进行字典查找，几乎不需要时间。值得注意的是，将预先计算好的边加入到图中的过程非常耗时，大约需要1.5分钟。这些计时在多次运行中保持一致。

我想说这个过程很好扩展，但我仍然在等待在一个空闲的电脑上（Athlon 64，每个处理器4800 BogoMIPS，全部在核心中），运行biggraph 5 6已超过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