Алгоритм для поиска самого длинного пути в орентированом графе?

Question

[ff0xff]

Доброе время суток, подскажите как называется алгоритм который позволяет
Найти самый длинный путь в ориентированном графе, где каждое ребро имеет вес.
( не используя тупой перебор )

Comments

[Wataru]

Нужны уточнения - ацикличен ли граф? Разрешается ли ходить по циклам, получая бесконечный путь?

[ff0xff]

Да, граф ацикличен, нет бесконечный путь получать нельзя.

[Wataru]

В ациклическом ориентированном графе, самое простое - это DFS. Рекурсивная функция, которая возвращает самый длинный путь с заданной вершины. С запоминантем ответа - если уже запускались с этой вершины, возвращаем уже подсчитанный результат. Иначе перебираем все ребра из этой вершины и берем максимум из dfs от конца ребра + длига ребра. Запоминаем этот максимум и возвращаем результат.

[ff0xff]

wataru, Оформите пожалуйста это как ответ, что бы я мог отметить это решением.

Answer 1

[Wataru]

В ациклическом ориентированном графе, самое простое - это DFS.
Рекурсивная функция, которая возвращает самый длинный путь с заданной вершины. С запоминантем ответа - если уже запускались с этой вершины, возвращаем уже подсчитанный результат. Иначе перебираем все ребра из этой вершины и берем максимум из dfs от конца ребра + длина ребра. Запоминаем этот максимум и возвращаем результат.

Comments

[longclaps]

запоминантем ответа - если уже запускались с этой вершины, возвращаем уже подсчитанный результат.

Туфта. При очередном заходе в вершину как знать, не содержит ли её "длиннейший путь" рёбер, которые уже были пройдены в этом заходе.

[ff0xff]

Ну дак элементарно, пройденное ребро удаляем.

[Wataru]

longclaps, Граф ациклический. Т.е. в нем нет циклов. Значит, все ребра в длиннейшем, да и любом, пути с вершины не могут быть в пути, который нас в нее привел.

[longclaps]

wataru, да, верно. В исходной задаче этого нет.

[longclaps]

ff0xff, не сработает. wataru предложил кешировать уже найденую длину наибольшего пути, этот кэш становится невалидным, если этот наибольший путь разрушен удалением ребра.

[Wataru]

longclaps, Да не надо ничего удалять. Мы в поиске в глубину уже к пройденному ребру никогда не придем в ациклическом графе. Никак, про него можно забыть, оно где-то сзади может быть в пути и учитывается только в верхних уровнях рекурсии.

Еще раз, функция от вершины возвращает самый длинный путь, начинающийся в ней. Что делает? Смотрит все исходящие ребра и вызвает себя от вершин детей. Поскольку граф ациклический, все пути из этих детей вершин никогда не вернутся в начальную вершину. Можно представить, что ребра к этим вершинам проста удалены из графа и это не изменит ответ никак.

Представте себе дерево подвешенное. В произвольном ациклическом графе чуть-чуть сложнее, но все тоже самое.

[longclaps]

wataru, всё верно - но в исходной задаче нет cлова ациклический.

[Wataru]

longclaps, Автор уточнил в комментарии под вопросом:
"ff0xff ff0xff Автор вопроса
Да, граф ацикличен, нет бесконечный путь получать нельзя. "

Answer 2

[ProfBiss]

Можете начать поиски отсюда Поиск самого длинного пути в направленном ацикличе...
Longest path problem

Comments

[longclaps]

Ну здравствуй, Гуглоперевод )