Все пути меньше данной длины в направленном графике между парой узлов

Question

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

Этот вопрос немного отличается, или, по крайней мере, я думаю.

ВХОД: Быть грамм направленный график. грамм могут иметь циклы, а также самосовершенствованные узлы. Позволять А (g) быть смежным матрицей грамм (с 1 в грамм_{я, j} Если есть ссылка, переходящая от I на J и 0 и 0 в противном случае). Определять Т а также Беременный Два подмножества узлов грамм, возможно, с пустого пересечения.

ИСХОД: Список всех путей длины в большинстве k Переход от одного узла в Т к одному узлу в Беременный. Анкет Пути могут содержать несколько раз на одних и тех же краях, если они переходят от исходного узла к целевому узлу в строго меньше, чем k+1 шаги.

ВОПРОС: Я хотел бы знать, какой алгоритм работает лучше всего в этой задаче. Я пытаюсь разработать возможный ответ, основанный на том факте, что N-й мощности матрицы смежности, если он символически вычисляется (с другой переменной для каждой записи вместо 1), сохраняйте тракты всех этих путей (и это Снижение подсчета путей, если вычисляется численно с помощью 1 в записях). Но я действительно не знаю, является ли это самым быстрым способом выполнения задачи (вероятно, нет).

ПРЕДОСТЕРЕЖЕНИЕ: Я не прошу проблему счета, ни о самых коротких путях, длина пути определяется как количество используемых краев (подсчет повторения). Я использую R, но если вы предпочитаете подумать об этом на любом другом языке! Мне очень жаль, если вопрос уже поставлен и решен. Спасибо за любую помощь!

Дополнительная информация: Я попробовал подход серии мощности матрицы (A^3 дает весь 3 длинного пути, ...) и DFS / BFS. Я думаю, что последние два далеки от оптимальности, так как они не принимают во внимание, что я работаю над наборами источников и целей, и, следовательно, выполняю много избыточной работы ...

Answer 1

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

1. Добавьте два новых узла $ S $ и $ T $,
2. Подключить $ S $ ко всем источникам,
3. Подключите все направления к $ t $.

После этого сокращения мы находимся в стандартной установке вопросов с двумя дополнительными вершинами $ S $ и $ T $, и мы хотим найти прогулки от $ S до $ T $ по длине по большей части $ K+2 $.