在加权有向图中使用DFS查找两个节点之间的所有路径
我有一个有向加权图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
共有1个答案
您的代码似乎是正确的（尤其是因为它适用于小图形）。
问题是节点之间可能有很多路径。对于完全连接的图，路径的数量是N的数量级！这是很多。由于您需要所有它们，因此您的程序会很慢（尤其是如果您用完ram并需要将东西交换到磁盘）。
如果您像在代码中那样限制最大总权重，假设所有权重都是一个，那么您仍然在O（权重）中运行，我假设您设置了一个较大的值，因为图形很大。
你需要弄清楚你是否真的需要所有这些路径。
如果您正在寻找最短路径，请使用Dijkstra或其他方法来查找最短路径。
-
我有一个有向加权图
-
我们希望您能够帮助我们解决以下问题： 给出了一个可能包含圈的有向图。必须找到一组满足以下标准的路径： 在从节点A到节点B的过程中可以通过的所有边必须被集合内的路径覆盖（一条边可以是集合中多条路径的一部分） 解决方案不必是路径数最少的解决方案，路径也不必是最短的。然而，该解决方案应该可以像java一样使用编程语言高效地实现。我们需要解决方案来生成几个测试用例，覆盖节点a和节点B之间的所有边很重要。
-
本文会围绕算法中DFS求有向图或无向图两点间所有路径，先讲解DFS以及有向图或无向图的意思。 有向图在图中的边是有方向的，表现出来就是有个箭头指示方向，节点只能单向通信或传递消息，相当于单行道，无向图边没方向是双向的，边连接的两个节点有通路可以双向通信，类似于双行道。 无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边。 DFS作为搜索算法
-
问题内容： 早上好！ 我正在开发一种算法，以查找无向图而不是加权图中的所有路径。我目前正在使用具有回溯功能的DFS算法来尝试执行此操作。这是我当前的代码： 该程序在其输入上接收整数。第一个是节点数，第二个是链接数，第三个是开始节点和结束音，它们是相同的。之后的所有整数表示节点之间的连接。 问题在于，该算法仅查找一次访问单个节点的所有路径。我想要的是仅查找一次访问每个连接的所有路径的算法。关于我该怎
-
我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径，但到目前为止，我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗？
-
我有一个未加权有向图G，它可能非常大（数千个节点）。