Алгоритм поиска различных путей от A до B в взвешенном ориентированном циклическом графе

Question

Предположим, у нас есть графики НАПРАВЛЕННЫЙ , ВЕСОВЫЙ и ЦИКЛИЧЕСКИЙ .

Предположим, нас интересуют только пути с общим весом менее MAX_WEIGHT

Какой алгоритм является наиболее подходящим (или каким-либо другим) для определения количества различных путей между двумя узлами A и B, общий вес которых меньше MAX_WEIGHT?

P.S: Это не моя домашняя работа.Просто личный некоммерческий проект.

Answer 1

Если количество узлов и кодовый кодовый код не слишком велико (и все веса являются целыми числами), вы можете использовать динамическое программирование

общий

инициализировать 0, кроме кода MAX_WEIGHT.

общий

решение - это сумма кода сгенерированного тега.

Answer 2

Простая рекурсия.У вас это экспоненциальное время.Очевидно, что циклы с нулевым весом не допускаются.

функция noe (узел N, предельный вес W)

1. нет.пути равен нулю, если все исходящие ребра имеют вес> W

2. в противном случае нет.пути - это сумма чисел пути, полученная суммой (noe (C1, W-W1), noe (C2, W-W2), ... noe (Cn, W-Wn)), где C1 ... Cn -узлов, подключенных к N, для которых W-Wi не является отрицательным, где Wi - вес соединяющего ребра, записанный на вашем любимом языке.

Должно существовать более эффективное решение в духе алгоритма Дейкстры, но я думаю, что этого достаточно для домашней работы.

Answer 3

Ваша проблема - это более общий случай K-непересекающийся путь в ориентированных планарных графах , с нефиксированной К.

Проблема с непересекающимися путями сгенерированного кода кода для ориентированных плоских графов выглядит следующим образом:

задано : ориентированный планарный граф G= (V; E) и k пар (r ₁ ; s ₁ ); ....; (r _k ; s _k ) вершин G;

find : k попарно непересекающихся вершинно направленных путей P ₁ ; ...; P _k в G, где P _i пробегает от r _i до s _i (i= 1; .. ..; л).

В k-непересекающемся пути вы можете нарисовать дугу от всех s _i до B, а также дугу от A до всех r _i , таким образом вы создадите граф G ' от Г.

Теперь, если вы можете решить свою проблему в G 'в P , вы можете решить k-непересекающийся путь в G, поэтому P= NP.

Но если вы прочитаете статью по ссылке, она дает некоторое представление об общем графике (решение k-непересекающегося пути с фиксированным k), и вы можете использовать его для получения хорошего приближения.

Также существует более сложный алгоритм, который решает эту проблему в P (при фиксированном k) в общих графах. но в целом это непросто (это Сеймур).

Итак, ваш лучший выбор в настоящее время - использовать алгоритмы грубой силы.

Изменить: поскольку MAXWEIGHT не зависит от размера вашего ввода (размера вашего графика), он не влияет на эту проблему. Кроме того, поскольку он NP-Hard для неориентированного невзвешенного графика, вы все же можете просто сделать вывод это NP-Hard.