大图作为输入以查找所有路径

Question

我正在使用以下 python 代码来查找每两个节点之间的所有路径。小图没问题。

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

for node3 in graph:
        for node4 in graph:
            few = bfs(graph, node3, node4)
            if not few == None:
                print ("{0} -> {1}".format(node3,node4))
                print (few)
                print ("\n")

但是，对于一个大约有 4K 个节点和 20K 个边的大图，我想找到每两个节点之间的所有路径。该程序中断并且不 return 任何输出。

请问如何设置输入图以及如何设置输出以添加到单独的文件中？

Answer 1

您的回答是可能无法完成，除非您的图是特殊图，路径数在这种图中的两个节点之间可能是 enormous.consider 以下情况：对于 200 个顶点和 20K 条边的完整图，任意两个顶点之间有 198!/2 条不同的路径。如果您的图表包含一个循环，那么其中就有无限条路径。
你的图可能在两个顶点之间有如此多的路径，即使是超级计算机也无法在十年内计算出这个数量。

大图作为输入以查找所有路径

Large graph as input to find all paths

python

graph

shortest-path

bigdata