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

Question

我有一个有向加权图G，其中权重是过渡的持续时间。

我使用经过修改的 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 并需要将内容交换到磁盘时)。

如果您像在代码中所做的那样限制最大总重量，假设所有权重都是一个，您仍然在 O(weight) 中运行，我假设您将其设置为一个较大的值，因为图表很大。

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

如果您正在寻找最短路径，请使用 Dijkstra 或其他工具来寻找最短路径。