Доброе утро, Тостер.
Пишу скрипт, который использует network -
https://networkx.readthedocs.io/
Все входные данные, заключены в файл. Все типичные задачи, типа построения графа, поиск короткого пути разобрался как решить, но не могу найти как можно вычислить самый длинный путь в графе.
Входные данные например такие:
Граф:
N1,N8
N2,N6
N3,N7,N1
N4,N2
N5,N8
N7,N2,N5,N4
N8,N7,N4
Поиск:
N1, *
В данном случае хочу получить:
N1,N8,N4,N2,N6 и N1,N8,N7,N2,N6
и собственно
path_length = 4
То есть нужно от N1 найти самый дальний узел и проложить к нему путь + посчитать длину.
Интересует решение исключительно с networkx, остальной функционал уже написан на нем.
UPDall_paths = []
for node in G:
all_paths.extend(find_paths(G, node, 6))
print all_paths
Вышеприведенный код находит все пути, для каждого узла в графе, где длина пути составляет 6.
Напомню, что я хочу найти самый длинный путь(пути) от определенного узла.
Заранее благодарен.
