两个节点之间的路径

Answer 1

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

Answer 2

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

Answer 3

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的网格图（可以很容易地由iggraph中的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。