我有一个有向图，包含源和目标。每个边的权重为1。节点没有权重。我需要找到一种有效的方法(我在C#上写，但我认为这不相关(，找到从源到目标的所有路径，路径的权重(或边的数量，与这些细节相同(小于或等于某个值，让我们称之为K。
我认为一种可能的方法是对从1到K的每个值运行Dijkstra，但由于K可能很大，所以效率不高。我一直在寻找一些答案，但也有一个与我的问题非常相似的问题，我觉得这个答案没有帮助。
(在直接加权图中找到从节点A到节点B的所有简单路径，权重之和小于某个值？(
您只需运行从源到目标的DFS即可分析所有路径。如果你必须找到当你到达深度K时停止的路径数量，返回0，当你到达目标时返回1，如果你也需要描述路径，你可以在使用DFS探索时构建一个树。复杂度为O(E(，其中E是边缘的数量
这里混合了python和伪代码：
def DFS(node, depth, target, visited, graph, max_depth):
visited.add(node)
if depth >= max_depth:
return Null
elif node == target:
return new_tree_node(node)
else:
sub_trees = list()
for connected_node in graph[node]:
if connected_node not in visited:
sub_tree = DFS(connected_node, depth+1, target, visited, graph, max_depth)
if sub_tree != Null:
sub_trees.append(sub_tree)
if length(sub_trees) > 0:
tree_node = new_tree_node(node)
for sub_tree in sub_trees:
tree_node.add_child(sub_tree)
return tree_node
else:
return Null
tree = DFS(source, 0, target, set(), graph, K)
PS：这个解决方案可以很容易地适应加权图以及