使用加權有向圖中的DFS查找兩個節點之間的所有路徑

Question

我有一個定向加權圖G，其中weight是轉換的持續時間。

我使用帶修改的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 

Answer 1

你的代碼似乎是正確的（特別是因爲它在小圖上工作）。

問題是節點之間可能有很多路徑。對於完全連通的圖，路徑的數量大約爲N！這是很多。既然你需要所有這些，你的程序會變得很慢（特別是如果你用完ram並需要將東西交換到磁盤）。

如果你像在代碼中那樣限制最大總重量，假設所有權重都是1，那麼你仍然運行在O（權重）中，我假設你設置爲一個很大的值，因爲圖形很大。

你需要弄清楚你是否真的需要所有這些路徑。

如果您正在尋找最短路徑使用Dijkstra或尋找最短路徑的東西。