Нахождение количества путей между двумя узлами в ориентированном графике ацикли c

Question

Моя идея решения этой проблемы состоит в том, чтобы настроить DFS так, чтобы он останавливался, когда мы попадаем на узел назначения, затем настраивал счетчик, который складывает всех соседей начального узла, затем соседей начального узла и его Соседи рекурсивно.

Мне просто интересно, будет ли при этом учитываться только путь от источника к месту назначения, а не какие-либо ошибочные пути, которые не ведут к узлу назначения.

Спасибо за Помогите.

Answer 1

Вы можете использовать динамическое программирование c. У вас есть ориентированный ациклический граф c, поэтому у вас есть узел (скажем, s) без дуг, указывающих на s. У вас также есть узел (скажем, t), у которого нет дуг, указывающих на t. Поскольку это acycli c, вы можете использовать алгоритм топологической сортировки , чтобы найти порядок узлов таким образом, что каждый ar c указывает в направлении от s и в направлении t.

начать с с. Количество путей от s до s равно 1, пустой путь. Поскольку граф ацикличен c, s должен иметь соседа u, так что единственный ar c, указывающий на u, это su. Теперь вы просто повторите. В общем, для узла w, который имеет дуги из v1, ... vk указывает на него. Тогда количество путей от s до w является просто суммой количества путей sv1, ..., путей svk.

Это в случае одного ar c между каждым узлом. Если есть несколько дуг, которые вы умножаете, то это будет (количество дуг v1w) (количество путей sv1) + ... + (количество дуг vkw) (количество путей svk)

И на каждом шаге вы можно использовать тот факт, что это acycli c, чтобы найти узел w такой, что вы уже вычислили все пути sv1 - svk.

Answer 2

Я бы использовал BFS.

Давайте назовем исходный узел s и целевой узел t.

Когда вы BFS начинаете с s, все пути с длиной 1 будет найден и помещен в очередь. Затем вы можете взять первый элемент очереди (назовите его u) и найти все пути размера 2 (s -> u -> ...). Повторяйте то же самое для каждого расстояния, пока не найдете все пути всех длин от s до t.

Уловка для его ускорения будет: после того, как вы исчерпали все пути узла w, запишите, сколько путей от w до t существует, и когда другой узел (выше w) достигнет w, вам не нужно будет повторно вычислять все пути.