Большой граф как вход для поиска всех путей

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 края. Программа прерывает и не возвращает никакого вывода.

Помогите мне, как установить входной график, а также как установить вывод для добавления в отдельный файл?

Answer 1

Ваш ответ может не может быть сделан,за исключением случая, что ваш график специального графика, количество путей между двумя узлами в такой графе может быть enormous.consider следующего случая: Для полный граф из 200 вершин и 20K краев есть 198!/2 разные пути между любыми двумя вершинами. Если ваш график содержит цикл, то есть бесконечный пути в нем.
В вашем графике может быть такое количество путей между двумя вершинами, что даже суперкомпьютер не смог вычислить число за десятилетие.