有向无环图中从源点到汇点的所有路径列表

Question

可能重复的问题：
[python]: 两个节点之间的路径

有没有人能给我一些资源，教我怎么做这个？我正在使用 networkx 这个Python库。

谢谢！

Answer 1

我不太确定有没有特别的优化方法——在寻找这些之前，我会先写一个简单的递归解决方案，类似于这样（使用networkx这个库时，只用到通过节点索引图形来获取邻居节点的功能[[在networkx中是一个字典，但我并不特别使用这个]])…：

def allpaths(G, source_nodes, set_of_sink_nodes, path_prefix=()):
  set_of_result_paths = set()
  for n in source_nodes:
    next_from_n = []
    for an in G[n]:
      if an in set_of_sink_nodes:
        set_of_result_paths.add(path_prefix + (n, an))
      else:
        next_from_n.append(an)
    if next_from_n:
      set_of_result_paths.update(
          allpaths(G, next_from_n, set_of_sink_nodes, path_prefix + (n,)))
  return set_of_result_paths

这个方法应该是可以证明是正确的（不过我不打算去证明，因为现在很晚了，我有点累，脑袋也有点糊涂；-)），而且可以用来验证后续的优化是否有效；-）。

我会尝试的第一个优化是简单的记忆化：如果我已经计算过从某个节点N到任何目标节点的路径集合（无论当时到达N的前缀是什么），我可以把这个结果存到一个字典里，键是N，这样下次如果我以不同的路径再次到达N，就可以避免重新计算；-）。

Answer 2

这个方法实际上可以在networkx中使用，而且它不是递归的，这对于处理大图来说可能会更好。

def find_all_paths(graph, start, end):
    path  = []
    paths = []
    queue = [(start, end, path)]
    while queue:
        start, end, path = queue.pop()
        print 'PATH', path

        path = path + [start]
        if start == end:
            paths.append(path)
        for node in set(graph[start]).difference(path):
            queue.append((node, end, path))
    return paths

Answer 3

这段内容是基于Alex Martelli的回答，但应该是可行的。它依赖于表达式source_node.children能够返回一个可迭代的对象，这样就可以遍历source_node的所有子节点。它还需要有一种有效的方法来比较两个节点，看看它们是否相同，使用is可能是更好的选择。显然，在你使用的库中，获取所有子节点的可迭代对象的语法是graph[source_node]，所以你需要相应地调整代码。

def allpaths(source_node, sink_node):
    if source_node == sink_node: # Handle trivial case
        return frozenset([(source_node,)])
    else:
        result = set()
        for new_source in source_node.children:
            paths = allpaths(new_source, sink_node, memo_dict)
            for path in paths:
                path = (source_node,) + path
                result.add(path)
        result = frozenset(result)
        return result

我主要担心的是，这种方法是深度优先搜索，当从源节点到某个节点（比如孙子、曾孙等）有多条路径时，会浪费很多计算资源，但这些路径不一定是到达目标节点的父节点。如果能为给定的源节点和目标节点缓存答案，就可以避免这些额外的计算。

下面是一个示例，说明这将如何工作：

def allpaths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong 
        memo_dict = dict()

    if source_node == sink_node: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = set()
            for new_source in source_node.children:
                paths = allpaths(new_source, sink_node, memo_dict)
                for path in paths:
                    path = (source_node,) + path
                    result.add(path)
            result = frozenset(result)
            # Memoize answer
            memo_dict[(source_node, sink_node)] = result
            return result

这也允许你在多次调用之间保存缓存字典，这样如果你需要计算多个源节点和目标节点的答案，就可以避免很多额外的工作。