高效地在大圖中找到最短路徑

Question

我正在尋找一種方法來實時查找巨大圖中節點之間的最短路徑。它有數十萬個頂點和數百萬條邊。我知道這個問題之前已經被問過了，我想答案是使用廣度優先搜索，但我更感興趣的是知道您可以使用哪些軟件來實現它。例如，如果它已經存在一個用於在無向圖中執行bfs的庫（帶有python綁定！），那將是完全完美的。

Answer 1

python-graph

補充說：

的評論讓我好奇的是，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邊緣也不算太壞。重要的是要注意，Dijkstra的方式是通過pygraph計算的，爲每個節點相對於一個目標生成所有生成樹的字典（該節點是任意節點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 

Answer 2

無向圖中的BFS只有大約25行代碼。你不需要一個圖書館。查看Wikipedia article中的示例代碼。

Answer 3

對於一個圖表，大（和你的性能限制），你可能想的Boost Graph Library，因爲它是用C++編寫。它有你正在尋找的Python bindings。

Answer 4

嗯，這取決於你有多少元數據附加到你的節點和邊緣。如果相對較少，圖形的大小將適合內存，因此我推薦使用純Python的優秀NetworkX軟件包（請參閱http://networkx.lanl.gov/reference/generated/networkx.shortest_path.html）。

對於一個更強大的解決方案，可以處理數百萬個節點，大型元數據，交易，磁盤存儲等，我已經與neo4j（http://www.neo4j.org/）很好運。它是用Java編寫的，但有Python綁定或可以作爲REST服務器運行。遍歷它是一個小竅門，但並不壞。

Answer 5

對於大圖，請嘗試Python接口igraph。它的核心是用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次）。這是第一個測試案例，如果您正在使用社交網絡數據或其他網絡，而網絡的直徑與網絡的規模相比較小，則這是合理的估計。第二個測試是一個幾何隨機圖，其中一個點在一個二維平面上隨機丟棄，如果它們的距離小於0.002，則連接兩個點，從而產生一個包含大約1M個頂點和6.5M邊的圖。在這種情況下，最短路徑計算需要更長的時間（因爲路徑本身更長），但它仍然非常接近實時：平均爲0.41357秒。

聲明：我是igraph的作者之一。

Answer 6

根據您擁有哪種附加信息，A *可能非常有效。特別是，如果給定一個節點，您可以計算從該節點到目標的成本估計值，A *是最優效率的。

Answer 7

店neo4j

它包括Dijkstra算法，A *， 「最短路徑」 算法。