[問題] 找graph中兩點的所有可能路徑
我目前的程式是要在圖中，找出特定兩點(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
推
12/09 02:23, , 1F
12/09 02:23, 1F
推
12/09 04:55, , 2F
12/09 04:55, 2F
推
12/09 11:45, , 3F
12/09 11:45, 3F
→
12/09 12:34, , 4F
12/09 12:34, 4F
→
12/09 13:48, , 5F
12/09 13:48, 5F
推
12/09 14:30, , 6F
12/09 14:30, 6F
→
12/09 22:08, , 7F
12/09 22:08, 7F
→
12/09 22:08, , 8F
12/09 22:08, 8F
→
12/09 22:10, , 9F
12/09 22:10, 9F
→
12/09 22:10, , 10F
12/09 22:10, 10F
→
12/09 22:11, , 11F
12/09 22:11, 11F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：
Python 近期熱門文章
PTT數位生活區 即時熱門文章
