两个节点之间的路径

Question

我正在使用networkx处理图。我有一个很大的图（其中有近200个节点），我尝试查找两个节点之间的所有可能路径。但是，据我了解，networkx只能找到最短的路径。如何不仅获得最短路径，还获得所有可能路径？

UPD：路径只能包含每个节点一次。

UPD2：我需要类似find_all_paths（）函数的功能，在此进行描述：python.org/doc/essays/graphs.html但是，此功能不适用于大量节点且边缘==

Answer 1

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...]

如果您拥有igraph 0.6或更高版本（在撰写本文时为开发版本），则也可以将结果限制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中。