algorithm - 带循环的遍历有向图

Question

我在 python 中使用 networkx 编写了一个脚本来构建有向图，我想获得从开始到结束的所有可能路径，包括循环。例如，有一个有向图:

我想获取这些路径:

A->B->D

A->B->C->D

A->B->C->B->D

A->B->C->B->C->B->D

...

据我所知，有很多算法可以找到 2 个节点之间的最短路径或没有循环的路径，但我想找到有循环的路径。

有什么算法可以实现吗？

非常感谢

Answer 1

如前所述，有无数条这样的路径。

但是，您仍然可以通过维护从一开始就可以到达的所有节点 v(以及您用来到达 v 的路径)以惰性方式生成所有这些节点k 步中的节点 k=1,2,...；如果 v 是您的目标节点，请记住它。

当您必须返回下一条路径时，(i) 从列表中弹出第一个目标节点，并且 (ii) 为列表中的所有非目标节点生成下一个候选节点。如果列表中没有目标节点，重复(ii)直到找到一个。

该方法在假设路径始终存在的情况下起作用。如果在 n-1 步中没有找到路径，其中 n 是节点数，只需报告不存在路径。

这是生成从最短到最长路径的算法的伪代码假设单位权重:

class Node {
    int steps
    Node prev

    Node(int steps=0, Node prev=null) {
        prev = prev
        steps = steps
    }
}

class PathGenerator {
    Queue<Node> nodes
    Node start, target;

    PathGenerator(Node start, Node target) {
        start = start
        target = target

        nodes = new Queue<>()
        nodes.add(start) // assume start.steps=0 and stat.prev=null
    }

    Node nextPath(int n) {
        current_length = -1;
        do {
            node = nodes.poll()
            current_length = node.steps
            // expand to all others you can reach from node
            for each u in node.neighbors()
                list.add(new Node(node, node.steps+1))
            // if node is the target, return the path
            if (node == target)
                return node
        } while (current_length < n);
       throw new Exception("no path of length <=n exists");
    }
}

请注意，列表 nodes 在最坏的情况下可能会呈指数增长(想想如果您在完整图上运行它会发生什么)。