igraph ， Python的另一个图形模块可以计算给定节点对之间的所有最短路径.计算所有路径没有意义，因为您有无数个这样的路径.

igraph, another graph module for Python can calculate all the shortest paths between a given pair of nodes. Calculating all the paths does not make sense as you have infinitely many such paths.

从顶点0计算所有最短路径的示例:

An example for calculating all the shortest paths from vertex 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的结果限制为给定的最终顶点:

If you have igraph 0.6 or later (this is the development version at the time of writing), you can restrict the result of get_all_shortest_paths to a given end vertex as well:

>>> 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的网格图(可以通过igraph中的Graph.Lattice([100, 100], circular=False)轻松生成).从左上角节点到右下角节点的最短路径数等于从200个元素中选择100个元素的可能性的数量(证明:最短路径的长度有200条边，其中100条会水平"走)在网格中，其中100个将垂直"移动).这可能不适合您的内存，因此，即使在这两个节点之间计算所有最短路径也不是真正可行的.

Of course you have to be careful; for instance, assume that you have a 100 x 100 grid graph (that can easily be generated by Graph.Lattice([100, 100], circular=False) in igraph). The number of shortest paths leading from the top left node to the bottom right node equals the number of possibilities to choose 100 elements out of 200 (proof: the length of the shortest path there has 200 edges, 100 of which will go "horizontally" in the grid and 100 of which will go "vertically"). This probably does not fit into your memory, therefore even calculating all the shortest paths between these two nodes is not really feasible here.

如果确实需要两个节点之间的所有路径，则可以使用igraph重写提到的网页上给出的功能，这可能比纯Python解决方案要快，因为igraph的核心是在C语言中实现的:

If you really need all the paths between two nodes, you can rewrite the function given on the webpage you mentioned using igraph, which will probably be faster than a pure Python solution as igraph's core is implemented in 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:

It can be optimized more by converting the graph to an adjacency list representation first as it would spare repeated calls to 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.

Edit: fixed first example to work in igraph 0.5.3 as well, not only in igraph 0.6.