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

Question

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

спасибо

Answer 1

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

Позволять min = min weight on the graph.
max = max weight on the graph.
Установите новые веса для всех ребер = wNew(e) = max - (wOld(e)-min).

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

Что если мы сейчас найдем кратчайший путь?

Answer 2

Просто отрицайте свои тяжелые весики и запустите кратчайший алгоритм пути (например, Bellman-Ford).

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

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

Answer 3

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

Это звучит как домашнее задание.