两个节点之间的路径

两个节点之间的路径

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中。