作者leolai (冰大鸟)
看板Python
标题[问题] 找graph中两点的所有可能路径
时间Wed Dec 9 00:13:00 2009
我目前的程式是要在图中，找出特定两点(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
1F：推 superGA:直觉是dynamic programming可以解决你的问题 （没仔细研究 12/09 02:23
2F：推 Lucemia:dp+1 12/09 04:55
3F：推 PsMonkey:他要「所有」路径耶... 炸掉很正常吧... XD 12/09 11:45
4F：→ ykjiang:你先惦惦看记忆体够不够你这样玩吧... 12/09 12:34
5F：→ KSJ:记忆体不够玩 硬碟够玩吗? 虽然比较慢 但会跑完吧? 12/09 13:48
6F：推 dotwsc:感觉用 generator 可以慢慢 enumerate 出所有路径 12/09 14:30
7F：→ yjc1:因为 python 对 recursion 不友善，预设 python recursion 12/09 22:08
8F：→ yjc1:depth 是 1000 (平台不同限制不同)，所以 > 1000 会挂是正常 12/09 22:08
9F：→ yjc1:解决方法：1. 自己做 TCO 改成 loop. 2. 用 sys module 中的 12/09 22:10
10F：→ yjc1:setrecursionlimit(limit)加大深度(太深一样会挂). 3 换演算 12/09 22:10
11F：→ yjc1:法. 4. 换 language.. (拖走…) 12/09 22:11