Python凍結路徑查找

我有一個腳本，它使用鄰接圖和BFS算法來查找兩點之間的路徑。有圖有大約10,000頂點和腳本設置這樣的：Python凍結路徑查找

graph = {... 
     '9660': ['9661', '9662', '9659'], 
     '9661': ['9654', '9660'], 
     '9662': ['9660', '9663'], 
     '9663': ['9664', '9662'], 
     '9664': ['9665', '9663'], 
           ...} 


def bfs(graph, start, end): 
# maintain a queue of paths 
queue = [] 
# push the first path into the queue 
queue.append([start]) 
while queue: 
    # get the first path from the queue 
    path = queue.pop(0) 
    # get the last node from the path 
    node = path[-1] 
    # path found 
    if node == end: 
     return path 
    # enumerate all adjacent nodes, construct a new path and push it into the queue 
    for adjacent in graph.get(node, []): 
     new_path = list(path) 
     new_path.append(adjacent) 
     queue.append(new_path) 

print bfs(graph, '50', '8659')

因爲這種算法適用於小鄰接圖，我猜蟒蛇只是需要一個很長的時間來處理這個大小的圖表。我的目標是找到最短的路徑，但是如果我甚至找不到一條路徑，那目前是不可能的。是否有python解決方案來處理使用大型鄰接圖的路徑查找？如果是這樣，我可以舉個例子嗎？

來源

2012-12-01 user1869328

最短路徑從哪裏到哪裏？ – irrelephant

首先使用深度，而你至少會找到一條我認爲的路徑...也許使它成爲一個發電機，因爲它也可能... –

我認爲你沒有跟蹤你已經訪問過的節點？ – irrelephant

您沒有記錄訪問過的節點，如果您的圖形不是有向非循環圖，這可能會導致大量浪費時間。例如，如果你的圖是

調用bfs(graph, 'A', 'Z')與算法將循環不必要通過「A」，「B」，「C」和「d」前最後到達Z.而如果你跟蹤訪問節點，您只需將「A」，「B」，「C」和「D」的鄰居每次添加到隊列中。

使用此版本的算法和字母圖形，這裏的隊列，並參觀了集將是什麼樣子的，而循環頂部貫穿整個算法：

queue = [ ['A'] ] 
visited = {} 

queue = [ ['A', 'B'], ['A', 'C'], ['A', 'D'], ['A', 'E'] ] 
visited = {'A'} 

queue = [ ['A', 'C'], ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], 
      ['A', 'B', 'D'] ] 
visited = {'A', 'B'} 

queue = [ ['A', 'D'], ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], 
      ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C'} 

queue = [ ['A', 'E'], ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'] ] 
visited = {'A', 'B', 'C', 'D'} 

queue = [ ['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'B', 'D'], ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'C', 'D'], ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'E', 'F'] ] 
visited = {'A', 'B', 'C', 'D', 'E'} 

queue = [ ['A', 'E', 'F', 'G'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F'} 

queue = [ ['A', 'E', 'F', 'G', 'H'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G'} 

... 
... 

queue = [ ['A', 'E', 'F', 'G', 'H', ..., 'X', 'Y', 'Z'] ] 
visited = {'A', 'B', 'C', 'D', 'E', 'F', 'G', ..., 'X', 'Y'} 

# at this point the algorithm will pop off the path, 
# see that it reaches the goal, and return

這是多少比添加諸如['A', 'B', 'A', 'B', 'A', 'B', ...]之類的路徑的工作更少。

來源

2012-12-04 12:27:35 Cyphase

Python凍結路徑查找

回答

相關問題