3
Как найти самый длинный путь на графике? Я думал, что могу использовать поиск по глубине, но я не мог найти для него более легкой реализации?Самый длинный путь графика
A
ответ
4
Как brainjam указал в комментариях, что это NP полный. он является только полиномиальным, если граф ацикличен. если его DAG - даже линейный. снова см. the wikipage для получения дополнительной информации.
+1
для довольно простого планарного графика, которое очень легко реализовать, чтобы получить все пути (=> получить длинный путь). смотрите здесь: http://stackoverflow.com/questions/2500877/count-of-distinct-acyclic-paths-from-aa-b-to-ac-d/2532646#2532646 (и просто используйте путь, который самый длинный), это должно дать вам представление о том, как можно сделать это с помощью общего графика: просто перебирайте все ребра текущей вершины вместо 4 следующих вызовов NextCell() – Karussell
0
сохранить длину/вес пути между каждым узлом как 1/(целое числом вашего/двойным/безотносительно), а затем использовать самый короткий путь, алгоритм,
+3
Я не думаю, что это сработает - рассмотрите случай, когда все веса ребер = 1 – gcbenison
1
попытаться использовать для топологической сортировки ориентированного графа. она предназначена специально для целей планирования задач ...
1
Если его DAG G = (V, E), вы можете просто сделать топологическую сортировку.
Затем вы отмечаете некоторый узел как s и t.
Тогда вы можете использовать динамическое программирование, где opt(I)= max(opt(j)+1) где j ребро (у, I) в Е.
Просто установите неавтоматические (s) = 0 и другой -INF, и игнорировать узлы, прежде чем с и после t в топологическом порядке (вы не можете достичь этих узлов из s, а после прохождения t вы не можете вернуться).
Обратите внимание, что его работа выполняется только для DAG (Direct Acitlic Graph).
Обратите внимание, что если это не DAG, вы можете умножить каждое ребро на -1, а затем использовать Bellman Ford, НО (!) Он не будет работать, если у вас будет отрицательный цикл.
Вы уверены, что не имеете в виду наибольшее расстояние между двумя узлами? –
Это может зависеть от правил и характеристик вашего графика. Разрешаете ли вы пересматривать узлы? Разрешаете ли вы ретушировать края? Может ли граф быть непересекающимся? Это направлено? Это ациклично? –
Это похоже на вариант для Traveling Salesman. Разве это даже разрешимо? –