在非循环有向图中查找两个节点之间所有路径的有效方法

Question

我想找到图中两个节点之间的所有路径。我编写了一个递归函数，它借助深度优先搜索算法找到所有路径。但是对于更大的图，它是非常低效的，所以我不能在我的程序中使用它。

我正在考虑针对我的问题实施迭代方法。这对我来说会非常耗时。那么有人知道这是否有意义吗？

在这种情况下，迭代方式是否更有效？或者是否可以优化我的递归方法？

我当前的功能：

function RecDFS(g::GenericGraph, visited)
    nodes = out_neighbors(visited[length(visited)], g) 

    for i in nodes
    if in(i,visited)
        continue
    end

    if i.label == "End"
        push!(visited,i)
        println(visited) # print every path from the first node in visited to the node with the label End
        pop!(visited)
        break
    end

    # continue recursive..
    for i in nodes
        if (in(i, visited) || i.label == "End")
            continue
        end
        push!(visited,i)
        depthFirstSearchAllI(g, visited)
        pop!(visited)
    end
end

Answer 1

您要解决的问题实际上是一个 NP-hard 问题，这意味着它还没有多项式时间算法！

因此您也许可以找到一些针对您的问题的优化方法，但是您无法运行足够快！

与优化一样，您可以执行以下操作。首先，您在问题主题中提到您的输入是 DAG 图，根据定义，DAG 具有以下属性:

DAG 的两个不同连接部分中的两个节点之间没有路径。

因此，如果您有一个列表，其中列出了 DAG 的哪个连接部分中有哪些节点（这可以在多项式时间内实现），您可以轻松地划掉很多无望的组合。

为了让您的程序迭代，您可以轻松地改用堆栈。只需将每个递归调用替换为 stack.push(node) 并将代码的遍历部分放入一段时间内（堆栈不为空），然后将节点一一弹出，除非有 none。应该可以了。

Answer 2

可以使用队列进行深度优先搜索，这样可以保存刚刚经过的节点。

Answer 3

对您的 DAG 中的顶点执行 topological sort，以获得 [v0, v1, ... , vn]。假设你的起始节点是vs，你的目的地是vt。 (如果s > t则没有路径)

然后，对于 s+1 .. t 中的每个 i，计算从 vs 到 vi 的路径 P(i)，如下所示：

如果有一条边vs -> vi，那就是一条路径（长度为 1）
找到所有 j 使得 s < j < i 并且有一条边 vj -> vi。添加通过从 P(j) 获取路径并附加边 vj -> vi
注意。对于给定的 i，不能保证存在从 vs 到 vi

正如已经评论过的那样，路径可以呈指数级增长，因此输出所有路径通常不能在小于指数级的时间内完成。但是，您可以使用这种方法以线性时间计算路径数。

Answer 4

经过一番思考，我找到了解决问题的好方法。看看这个示例代码：

function RecDFS(g::GenericGraph, visited)
   nodes = out_neighbors(visited[length(visited)], g) 
   if(checkPath(visited))
       for i in nodes
           if in(i,visited)
              continue
           end

           if i.label == "End"
               push!(visited,i)
               println(visited) # print every path from the first node in visited to the node with the label End
               pop!(visited)
               break
           end
        end

   # continue recursive..
       for i in nodes
           if (in(i, visited) || i.label == "End")
               continue
           end
           push!(visited,i)
           depthFirstSearchAllI(g, visited)
           pop!(visited)
       end
   end
end

总而言之，我刚刚添加了一个额外的 if 语句。函数 checkPath(visited) returns true，如果路径到现在都有效。如果路径（或路径的一部分）无效，则函数结束。

对于我的具体问题，这是一个很好的解决方案。它在我的测试中快了 100 倍运行，对于我最大的问题实例，它有 500 个节点和 16000 个边，只需要 15 秒。

非常感谢 Ashkan Kzme 和 Rob 的帮助。

在非循环有向图中查找两个节点之间所有路径的有效方法

Efficient way to find all paths between two nodes in a non-cyclical directed graph

algorithm

network-programming

graph

data-structures

julia