两个节点之间的路径

Question

我正在使用networkx来处理图形。我有一个相当大的图（里面有近200个节点），我想找到两个节点之间的所有可能路径。但是，按照我的理解，networkx只能找到最短路径。我该如何获取不仅仅是最短路径，而是所有可能的路径呢？

更新：路径中每个节点只能出现一次。

更新2：我需要类似于find_all_paths()这个函数，具体描述可以在这里找到：python.org/doc/essays/graphs.html。但是这个函数在处理大量节点和边时效果不好 =(

Answer 1

Dijkstra算法可以找到最短路径，它的工作方式有点像广度优先搜索（BFS），不过它用的是一个优先队列，这个队列根据深度来给图中的节点排序，而不是像BFS那样用普通的队列。如果你需要找到多个最短路径，其实可以很简单地扩展这个算法来得到'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

igraph是一个用于Python的图形模块，它可以计算给定两个节点之间的所有最短路径。不过，计算所有路径并没有意义，因为这样的路径是无限的。

下面是一个从节点0计算所有最短路径的例子：

>>> from igraph import Graph
>>> g = Graph.Lattice([10, 10], circular=False)
>>> g.get_all_shortest_paths(0)
[...a list of 3669 shortest paths starting from vertex 0...]

如果你使用的是0.6版本或更高版本的igraph（截至目前，这个版本是开发版），你还可以将get_all_shortest_paths的结果限制到一个特定的终点节点：

>>> g.get_all_shortest_paths(0, 15)
[[0, 1, 2, 3, 4, 14, 15],
 [0, 1, 2, 12, 13, 14, 15],
 [0, 10, 11, 12, 13, 14, 15],
 [0, 1, 11, 12, 13, 14, 15],
 [0, 1, 2, 3, 13, 14, 15],
 [0, 1, 2, 3, 4, 5, 15]]

当然，你需要小心；比如说，假设你有一个100 x 100的网格图（可以通过Graph.Lattice([100, 100], circular=False)在igraph中轻松生成）。从左上角节点到右下角节点的最短路径数量等于从200个元素中选择100个的可能性（证明：这条最短路径的长度有200条边，其中100条在网格中是“水平”的，100条是“垂直”的）。这可能会超出你的内存限制，因此在这种情况下，计算这两个节点之间的所有最短路径实际上是不可行的。

如果你真的需要计算两个节点之间的所有路径，你可以使用你提到的网页上的函数，改写成使用igraph的版本，这样可能会比纯Python的解决方案更快，因为igraph的核心是用C语言实现的：

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in set(graph.neighbors(start)) - set(path):
        paths.extend(find_all_paths(graph, node, end, path))
    return paths

通过先将图转换为邻接表的表示方式，可以进一步优化，因为这样可以避免重复调用graph.neighbors：

def find_all_paths(graph, start, end):
    def find_all_paths_aux(adjlist, start, end, path):
        path = path + [start]
        if start == end:
            return [path]
        paths = []
        for node in adjlist[start] - set(path):
            paths.extend(find_all_paths_aux(adjlist, node, end, path))
        return paths

    adjlist = [set(graph.neighbors(node)) for node in xrange(graph.vcount())]
    return find_all_paths_aux(adjlist, start, end, [])

编辑：修正了第一个例子，使其在igraph 0.5.3中也能工作，而不仅仅是在igraph 0.6中。