[問題] 找graph中兩點的所有可能路徑

[leolai (冰大鳥)]

我目前的程式是要在圖中，找出特定兩點(u,v)的所有路徑
例如:
      0--------1
      |\       |
      | \      |   (0,3)的所有路徑為[0,3],[0,1,3],[0,2,3]
      |  \     |
      |   \    |
      |    \   |
      |     \  |
      |      \ |
      2--------3

以下是我的程式碼:
import networkx
  .
  .
  .

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
       return [path]
    if not graph.has_node(start):
       return []
    paths = []
    for node in graph.neighbors(start):
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

目前這段程式碼可以正確跑出結果，但問題在於當節點數太多時(>1000)
邊的數量也多，如果要跑完圖中全部pair的所有可能路徑
會花上許多時間，甚至程式就直接當掉

想請問板上的大家，針對這樣的問題不知有什麼較好的解決方法
謝謝



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.10.29
推 superGA:直覺是dynamic programming可以解決你的問題 （沒仔細研究
推 Lucemia:dp+1
推 PsMonkey:他要「所有」路徑耶... 炸掉很正常吧... XD
→ ykjiang:你先惦惦看記憶體夠不夠你這樣玩吧...
→ KSJ:記憶體不夠玩  硬碟夠玩嗎? 雖然比較慢  但會跑完吧?
推 dotwsc:感覺用 generator 可以慢慢 enumerate 出所有路徑
→ yjc1:因為 python 對 recursion 不友善，預設 python recursion
→ yjc1:depth 是 1000 (平台不同限制不同)，所以 > 1000 會掛是正常
→ yjc1:解決方法：1. 自己做 TCO 改成 loop. 2. 用 sys module 中的
→ yjc1:setrecursionlimit(limit)加大深度(太深一樣會掛). 3 換演算
→ yjc1:法. 4. 換 language.. (拖走…)