Найти самый длинный путь в ориентированном циклическом графе от источника s до пункта назначения f.Предположим, что не существует положительных циклов веса

Question

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

спасибо

Answer 1

Просто отрицайте вес ребер и запустите алгоритм кратчайшего пути (например, Беллман-Форд).

Циклы с нулевым весом могут быть проблемой. Вам нужно будет разорвать связи на своих путях, выбрав самый короткий (по длине, а не по весу). Один из способов сделать это - сделать ваши веса парными (- (исходный вес), 1), сложить их попарно и выполнить лексикографическое упорядочение.

См. Также Самый длинный путь между двумя вершинами

Answer 2

Я не уверен, что это будет работать (нужно проверить это), но ... вы можете сделать что-то похожее на:

Let min = min weight on the graph.
max = max weight on the graph.
Setновые веса для всех ребер = wNew(e) = max - (wOld(e)-min).

Теперь есть отрицательные весы, и весы находятся в обратном порядке (то есть, если w(e1) было больше, чем w(e2), теперь оно меньше).

Что если мы сейчас ищем самый короткийпуть

Answer 3

Если вы получили DCG, вы можете просто зацикливаться вечно, прежде чем доберетесь до своей цели, это будет «самый длинный путь». В этом случае вопрос является неполным, и алгоритм, вероятно, выглядит по-разному в зависимости от специфики.

Звучит как домашняя работа.