Начиная с некоторой вершины, как найти самый длинный путь относительно этой вершины? Я просмотрел все и не могу найти решение этой проблемы, которое действительно работает для всех возможных случаев DAG. Исходный код в NetworkX был бы предпочтительнее, но и обычный python тоже подойдет. Мне искренне любопытно, почему мне не удается найти подходящий рабочий пример, я понимаю, что это проблема NP-типа, но я хотел бы знать, как это сделать наиболее эффективно.
Самый эффективный способ NetworkX найти самый длинный путь в DAG в начальной вершине без ошибок
comment
Добро пожаловать в Stack Overflow! Кажется, вы просите кого-нибудь написать код для вас. Stack Overflow — это сайт вопросов и ответов, а не сервис написания кода. Пожалуйста, см. здесь, чтобы узнать, как писать эффективные вопросы.
- person LinkBerest schedule 27.09.2016
Ответы (1)
Во-первых, я бы проверил, связен ли этот граф. Если это так, то самый длинный путь — это путь через все узлы. Если нет, значит, эта вершина содержится в компоненте связности. Затем я бы использовал connected_component_subgraphs , чтобы найти самый большой компонент, в котором находится эта вершина. После этого самым длинным путем будет путь через все узлы в этом самом большом компоненте.
Конечно, это работает, только если вы не разрешаете циклы на своем пути.
import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(0,1),(0,4),(4,5),(4,6),(5,6),(6,1),(0,2),(2,3),(1,2)])
for path in nx.all_simple_paths(G, source=0, target=3):
print(path)
Результат:
[0, 1, 2, 3]
[0, 2, 3]
[0, 4, 5, 6, 1, 2, 3]
[0, 4, 6, 1, 2, 3]
Третий - то, что вам нравится.
person
mengg
schedule
25.09.2016
Я понимаю логику этого, но я очень долго пытался решить эту проблему, я нахожусь в точке, где мне просто нужно узнать правильный исходный код.
- person tohnotakaki; 25.09.2016
Имейте в виду, я также хочу знать очень эффективный способ сделать это, грубая форсировка путей - это не то, что я хотел бы делать. Я хотел бы получить исходный код в духе более эффективного грубого перебора, то есть вычисления некоторого пути, начинающегося с вершины, и, если вершина будет обнаружена в другой итерации, мы можем просто вскоре закончить, добавив текущий путь к уже вычисленный путь
- person tohnotakaki; 25.09.2016
Я думаю, что весь алгоритм поиска по графу в NetworkX основан на грубой силе. Также я не понимаю, почему
dfs_tree не соответствует вашим потребностям.
- person mengg; 25.09.2016
Поскольку он не даст нам самого длинного пути, если мы проведем поиск в глубину дерева, он даст нам путь, но если мы подумаем об альтернативном пути от корня, который может соединиться с уже видимым путем, он не вернет путь. сумма длины этих двух путей не так ли? Или я ошибаюсь
- person tohnotakaki; 26.09.2016
Я не совсем понимаю, как dfs даст вам самый длинный путь в дереве, см. [link]imgur.com /EcTcpZv[ссылка] самый длинный путь явно равен 6, но самый длинный путь из dfs даст 3, так как ребро от '6' до '1' уже было посещено ранее. Если мы проигнорируем часть о графах с петлями, каков наиболее точный способ найти самый длинный путь?
- person tohnotakaki; 26.09.2016
Ты прав. Ни BFS, ни DFS не ориентированы на кратчайший путь. Но я нахожу эту функцию
all_simple_path. Я проверил на графике, который вы создали. Я просто добавляю пример кода выше в ответ.
- person mengg; 26.09.2016
Это также неверно в том случае, если я не знаю, какая у меня конечная вершина правильная? Если мне дадут несколько графиков, на которых я не знаю, что является целью, я не смогу найти самый длинный путь.
- person tohnotakaki; 26.09.2016
Так что насчет случая, когда вы не знаете цель?
- person tohnotakaki; 26.09.2016
Затем вы можете опустить аргумент
target.
- person mengg; 26.09.2016
