Большой график в качестве входных данных, чтобы найти все пути

python graph shortest-path bigdata

399 просмотра

1 ответ

16 Репутация автора

Я использую следующий код 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 ребрами. Программа прерывается и не возвращает никакого вывода.

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

Автор: Siavash R Источник Размещён: 18.07.2016 08:24

Ответы (1)


0 плюса

464 Репутация автора

Решение

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

Автор: FazeL Размещён: 18.07.2016 11:40
Вопросы из категории :
32x32