python 两个节点之间的路径

Path between two nodes

提问by user285070

I'm using networkx to work with graphs. I have pretty large graph (it's near 200 nodes in it) and I try to find all possible paths between two nodes. But, as I understand, networkx can find only shortest path. How can I get not just shortest path, but all possible paths?

我正在使用 networkx 来处理图表。我有非常大的图（它有近 200 个节点），我尝试找到两个节点之间的所有可能路径。但是，据我所知，networkx 只能找到最短路径。我怎样才能不仅获得最短路径，而且获得所有可能的路径？

UPD: path can contain each node only once.

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

UPD2: I need something like find_all_paths() function, described here: python.org/doc/essays/graphs.html But this function doesn't work well with large number of nodes and edged =(

UPD2：我需要类似 find_all_paths() 函数的东西，这里描述：python.org/doc/essays/graphs.html 但是这个函数不能很好地处理大量节点和边缘 =(

回答by Tamás

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

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

An example for calculating all the shortest paths from vertex 0:

计算从顶点 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...]

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_pathsto a given end vertex as well:

如果您有 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]]

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 shortestpaths between these two nodes is not really feasible here.

当然你要小心；例如，假设您有一个 100 x 100 的网格图（可以Graph.Lattice([100, 100], circular=False)在 igraph 中轻松生成）。从左上角节点到右下角节点的最短路径数等于从 200 个元素中选择 100 个元素的可能性数（证明：最短路径的长度有 200 条边，其中 100 条将“水平”在网格中，其中 100 个将“垂直”）。这可能不适合您的记忆，因此即使计算这两个节点之间的所有最短路径在这里也不可行。

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:

如果你真的需要两个节点之间的所有路径，你可以使用 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

It can be optimized more by converting the graph to an adjacency list representation first as it would spare repeated calls to graph.neighbors:

可以通过首先将图形转换为邻接列表表示来对其进行更多优化，因为这样可以避免重复调用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, [])

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

编辑：修复第一个示例也可以在 igraph 0.5.3 中工作，而不仅仅是在 igraph 0.6 中。

回答by bukzor

This one actually works with networkx, and it's non-recursive, which may be nice for large graphs.

这个实际上适用于 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

回答by ConcernedOfTunbridgeWells

Dijkstra's algorithm will find the shortest path in a manner similar to a breadth first search (it substitutes a priority queue weighted by depth into the graph for the naive queue of a BFS). You could fairly trivially extend it to produce the 'N' shortest paths if you need some number of alternatives, although if you need the paths to be substantially different (e.g. scheduling the routes of security vans) you might need to be more clever about selecting paths that are significantly different from each other.

Dijkstra 算法将以类似于广度优先搜索的方式找到最短路径（它将深度加权的优先级队列替换为 BFS 的朴素队列的图中）。如果您需要一些替代方案，您可以相当简单地扩展它以生成“N”条最短路径，但如果您需要路径大不相同（例如安排安全车的路线），您可能需要更聪明地选择彼此显着不同的路径。