使用加权有向图中的DFS查找两个节点之间的所有路径

我有一个定向加权图G，其中weight是转换的持续时间。使用加权有向图中的DFS查找两个节点之间的所有路径

我使用带修改的DFS编写了两个顶点之间的所有路径搜索算法：搜索继续进行，直到路径的总权重（其各部分的权重之和）将少一些值。我的代码在小图中工作，但在大图（| V | = 1800，| E | = 50870）中它会冻结。

def find_paths(self, start, end, weight_limit=10): 
     res = [] 

     def dfs(start, end, path=[], weight=0): 
      path = path + [start] 
      if len(path) > 1: 
       weight += self.weights[(path[-2], start)] 
      if weight > weight_limit: 
       return [] 
      if start == end: 
       res.append((path, weight)) 
       return [path] 
      if start not in self.adjacent: 
       return [] 
      paths = [] 
      for node in self.adjacent[start]: 
       if node not in path: 
        paths.extend(dfs(node, end, path, weight)) 
      return paths 

     dfs(start, end) 
     return res

来源

2016-04-26 Andrei

可能是内存错误。你真的需要跟踪所有的路径和他们的权重？ –

@JaredGoguen是的，我需要跟踪所有路径及其权重，因为我的目标是查找GRAPH中START和END节点之间的所有路径。所以，如果这是内存错误，是否有可能解决这个问题？有任何想法吗？ – Andrei

路径总数可能随着边缘数量的增加而有规模地增长。甚至50！太大而无法通过枚举来处理，不介意50000！ –

你的代码似乎是正确的（特别是因为它在小图上工作）。

问题是节点之间可能有很多路径。对于完全连通的图，路径的数量大约为N！这是很多。既然你需要所有这些，你的程序会变得很慢（特别是如果你用完ram并需要将东西交换到磁盘）。

如果你像在代码中那样限制最大总重量，假设所有权重都是1，那么你仍然运行在O（权重）中，我假设你设置为一个很大的值，因为图形很大。

你需要弄清楚你是否真的需要所有这些路径。

如果您正在寻找最短路径使用Dijkstra或寻找最短路径的东西。

来源

2016-04-26 15:30:40 Sorin

详细说明“Dijkstra什么的”http://cs.stackexchange.com/questions/2942/am-i-right-about-the-differences-between-floyd-warshall-dijkstra-and-bellman-fo – Matsmath

@ Sorin不，我需要两个节点之间的所有路径（没有周期）。我不需要找到最短路径，我需要找到total_weight <确定值的路径 – Andrei

使用加权有向图中的DFS查找两个节点之间的所有路径

回答

相关问题