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

Question

У меня есть ориентированный граф с взвешенными ребрами (все веса положительные).

Теперь я ищу эффективный алгоритм или код (в частности, C #), чтобы найти самый длинный путь между двумя заданными вершинами.

Answer 1

Это в точности эквивалентно алгоритму кратчайшего пути со всеми отрицательными весами. Для этого вам необходимо убедиться, что нет циклов с отрицательным весом (что в вашем исходном случае, вероятно, эквивалентно проверке отсутствия циклов с положительным весом). Лучше всего взять аддитивную обратную величину от веса и запустить Беллмана-Форда, а затем принять аддитивную обратную величину результата.

Answer 2

Ответ Дэвида Бергера верен, если только вы не имеете в виду простой путь, где каждая вершина может встречаться не более одного раза, и в этом случае Беллман-Форд не даст самый длинный путь. Поскольку вы говорите, что веса положительные, самый длинный путь может существовать, когда у графа есть цикл (достижимый из источника), если вы не имеете в виду простой путь. Самая длинная проблема простого пути - NP-полная. См. Википедия .

Итак, давайте предположим, что вы имеете в виду ориентированный ациклический граф (DAG). В линейном времени вы можете вычислить самый длинный путь к каждой вершине v из начальной вершины s, учитывая, что вы знаете самый длинный путь из s -> * u для каждого u, где u-> v напрямую. Это просто - вы можете выполнить поиск в глубине на вашем ориентированном графе и вычислить самый длинный путь для вершин в обратном порядке их посещения. Вы также можете обнаружить задние кромки всей вашей DFS, используя 3-цветную маркировку (открытые, но не законченные вершины серого цвета). Смотрите Wikipedia снова для получения дополнительной информации. Поиск самого длинного / самого короткого пути в группе обеспечения доступности баз данных иногда называют алгоритмом Витерби (даже если он был задан в предположении, что используется определенный тип группы доступности базы данных).

Сначала я бы попробовал решение для динамического программирования с линейным временем. Если у вас есть циклы, то Bellman-Ford все равно не решит вашу проблему.

Answer 3

Пожалуйста, обратитесь к проекту QuickGraph , поскольку он предоставляет структуры данных .NET, реализующие графы, а также предоставляет алгоритмы для работы с такими структурами данных. Я уверен, что алгоритм, который вы ищете, реализован в библиотеке.

Answer 4

На всякий случай, если это кому-нибудь поможет, так как я некоторое время искал это, но не мог его найти, я использовал QuickGraph , чтобы решить проблему, когда мне нужно было найти самый длинный путь, который также соответствует с определенным правилом. Это не очень элегантно, так как я сделал это немного грубо, как только получил первый результат, но вот оно.

https://github.com/ndsrf/random/blob/master/LongestSkiPath/LongestSkiPath/SkiingResolver.cs#L129-L161

Чтобы получить самый длинный путь, вы используете алгоритм, чтобы найти самый короткий путь с длинами = -1. А затем, чтобы найти последующие самые длинные пути, я начинаю удалять ребра с этого самого длинного пути, чтобы посмотреть, удастся ли мне получить «лучший» (в зависимости от условий задачи) самый длинный путь.