枚举有向无环图中的所有路径

Question

有没有标准算法可以在有向a循环图中找到所有可能的路径。如果没有，我如何在BFS/Dijkstra/任何其他算法中进行更改，以枚举DAG 中的所有路径

Answer 1

在Exponential中查找任何图中的所有可能路径。它可以通过使用回溯来解决。对于DAG，我们可以使用深度优先搜索（DFS）。在DFS代码中，从任何节点开始，转到极端死胡同路径，并使用一些数组或列表记下该路径中访问的所有节点。一旦找到死胡同，打印包含访问节点的数组，弹出最后一个存储的节点，从第（n-1）个节点的另一个路径开始。如果第（n-1）个节点的所有路径都用完了，则从列表中弹出该节点并从（n-2）个节点开始。这样做，直到你到达所有的死胡同并到达第一个节点。所有打印的路径都是给定DAG中的路径。

你可以检查代码http://pastebin.com/p6ciRJCU

Answer 2

下面是一个经过修改的DFS的简短python示例：

data = {1 : [2,3],   # Directed acyclic graph adjacency list
        2 : [3],
        3 : [4,5],
        4 : [5],
        6 : [7,8]}   # These nodes are disconnected from the rest of the graph
def dfs(data, path, paths):
    datum = path[-1]              
    if datum in data:
        for val in data[datum]:
            new_path = path + [val]
            paths = dfs(data, new_path, paths)
    else:
        paths += [path]
    return paths
def enumerate_paths(graph):
    nodes = list(graph.keys())
    all_paths = []
    for node in nodes:
        node_paths = dfs(graph, [node], [])
        all_paths += node_paths
    return all_paths

输入：

enumerate_paths(data)

输出：

[[1, 2, 3, 4, 5], [1, 2, 3, 5], [1, 3, 4, 5], [1, 3, 5], [2, 3, 4, 5], [2, 3, 5], [3, 4, 5], [3, 5], [4, 5], [6, 7], [6, 8]]

Answer 3

我的想法是扩展所有路径，从在没有候选路径的情况下插入第一条边开始，然后在路径集中的头部、尾部扩展每条边，或者在考虑的边产生分歧（冲突路径）时拆分路径。

这是一种基于稳定性思想的迭代方法：每次考虑所有边，如果在一个转弯中没有动作要做，那么转弯是稳定的，没有更多的动作要做。这种方法要注意的一点是不要过早分叉：第一个转弯是准备转弯，所以分叉阶段只在下一个转弯时激活。我正在评估交替分叉和扩展相位是否更好（我的意思是：更正确），并将stable_turn视为稳定的两个转弯

这里的代码：

https://gist.github.com/danielecr/6abd8ad48461347238ad1caf3714fe6a

（对不起，这是javascript，不太容易阅读，但我需要这个语言）