两个节点之间的路径

Question

两个节点之间的路径

pythonnetworkxigraph

9

我正在使用networkx处理图形。我有一个相当大的图形(它有近200个节点)，我试图找到两个节点之间的所有可能路径。但是，据我所知，networkx只能找到最短路径。如何获得不仅仅是最短路径，而是所有可能的路径？

更新: 路径只能包含每个节点一次。

更新2: 我需要类似于find_all_paths()函数的东西，在这里描述: python.org/doc/essays/graphs.html 但是这个函数在处理大量节点和边时效果不好 =(

- user285070

1

一般来说，这是不可能的。如果你的图中存在循环，那么就会有无限条路径，例如 A->B->A->B->...->B->C。你需要在问题中添加一些额外的限制条件（例如禁止循环，或者如何处理循环）。 - Mark Byers

虽然你可以使用乌龟和兔子算法检测路径中的循环，但是结合广度优先搜索可能会得到一个可接受的近似值，尽管我敢说这可能会有些低效。 - ConcernedOfTunbridgeWells

我需要类似于 find_all_paths() 函数的东西，可以在这里找到描述: http://www.python.org/doc/essays/graphs.html 但是该函数在处理大量节点和边时效果不佳 =( - user285070

@user285070的链接已经失效，但是我无法编辑评论，所以这里提供了修正后的链接：https://www.python.org/doc/essays/graphs/。如果您更喜欢使用wayback缓存，请访问：http://wayback.archive.org/web/20131102032815/http://www.python.org/doc/essays/graphs.html。 - Matthew Cornell

3个回答

11

这个方法可以在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

- bukzor

这段代码是否计算了任意两个节点之间的所有可能路径？包括最短路径和较长的路径？ - FaCoffee

0

Dijkstra算法将以类似于广度优先搜索的方式找到最短路径（它使用了一个与深度加权的优先队列替代了BFS中简单的队列）。如果你需要一些备选方案，你可以相对轻松地扩展它以产生“N”条最短路径，尽管如果你需要路径在很大程度上不同（例如安排保安车的路线），你可能需要更巧妙地选择彼此之间有显著区别的路径。

- ConcernedOfTunbridgeWells

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tamás · Accepted Answer

Python-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的网格图（可以通过igraph中的Graph.Lattice([100, 100], circular=False)轻松生成）。从左上节点到右下节点的最短路径数量等于从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 中都可以工作。