Как найти сколько путей в графе

Автор – Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

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

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Введение

Если G является неориентированным графом, то путём в графе G будет такой конечный или бесконечный набор последовательных рёбер и вершин S = (…, a0, E0, a1, E1, …, En-1, an), для которого пара соседних рёбер Ei и Ei-1 обладают общей вершиной ai. То есть справедливы следующие выражения E0 = (a0, a1), E1 = (a1, a2), …, En = (an, an+1)

Следует заметить, что возможна неоднократная встреча с одним и тем же ребром при прохождении путевого маршрута. В случае, когда нет рёбер, которые предшествуют E0, то a0 считается исходной вершиной S. А когда не существует рёбер, которые идут за E(n-1), то an считается последней вершиной S. Все вершины, которые принадлежат паре соседних рёбер, считаются внутренними.

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

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

Путь, при котором нет рёбер графа, соединяющих две вершины пути, носит название индуцированного пути. Пара путей считается независимой в смысле вершин, когда у них нет одинаковых внутренних вершин. И по аналогии пара путей считается независимой в плане рёбер, когда у них нет общих внутренних рёбер.

Количество путей в графе

В случае, когда в город S возможно доехать лишь из городов X, Y, и Z, то количество разнообразных путевых маршрутов из города А в город S равняется суммарному количеству разных путей движения из А в Х, из А в Y и из А в Z, что можно выразить следующей формулой:

$N_S = N_X + N_Y + N_Z$

Обозначим как NM количество путевых маршрутов из вершины А в некую вершину М. Количество путей будет конечным, если в графе отсутствуют замкнутые пути, то есть циклы. Рассмотрим конкретный пример. Имеется структурная схема дорог, которые соединяют города А, Б, В, Г, Д, Е, Ж, И, К, Л. Передвижение по всем дорогам возможно только в одну сторону, в которую указывает стрелка. Необходимо определить количество возможных путей из города А в город Л.

Обозначим как $N_X$ число разных маршрутов из города А в город Х. Считаем, что город А является исходным пунктом путевого маршрута, и, следовательно, NA = 1. А для произвольно выбранного города Х число путей $N_X$ возможно определить по формуле:

$N_X = N_Y + … + N_Z$.

Здесь суммарный путь принят по всем вершинам, имеющим прямую связь с вершиной Х, то есть, к примеру:

$N_Л = N_Д + N_И + N_Ж + N_К$

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

В пункты Б и В ведут единственные дороги из А. В пункт В можно попасть из пунктов А, Б, и Г, т.е. $N_В = N_А + N_Б + N_Г = 3$.

В пункт Е можно попасть только из Г, количество путей равно количеству путей в пункт Г. В пункт Ж ведут прямые пути из пунктов Е и В, т.е. $N_Ж = N_В + N_Е = 4$. В пункт Д ведут прямые пути из пунктов Б и В, т.е. $N_Д = N_В + N_Б = 4$.

В пункт И можно попасть только из Д, количество путей равно количеству путей в пункт Д = 4. В пункт К ведет путь только из пункта Е, т.е. $N_К = N_Е = 1$. В пункт Л ведут прямые пути из пунктов Д, И, Ж и К, т.е. $N_Л = N_Д + N_И + N_Ж + N_К = 13$.

Итоговый результат тринадцать путей.

Count the total number of ways or paths that exist between two vertices in a directed graph. These paths don’t contain a cycle, the simple enough reason is that a cycle contains an infinite number of paths and hence they create a problem

Examples: 

For the following Graph:

Input: Count paths between A and E
Output: Total paths between A and E are 4
Explanation: The 4 paths between A and E are:

                      A -> E
                      A -> B -> E
                      A -> C -> E
                      A -> B -> D -> C -> E 

Input: Count paths between A and C
Output: Total paths between A and C are 2
Explanation: The 2 paths between A and C are:

                      A -> C
                      A -> B -> D -> C

Count paths between two vertices using Backtracking: 

To solve the problem follow the below idea:

The problem can be solved using backtracking, which says to take a path and start walking on it and check if it leads us to the destination vertex then count the path and backtrack to take another path. If the path doesn’t lead to the destination vertex, discard the path. This type of graph traversal is called Backtracking.

Backtracking for the above graph can be shown like this: 

Note: The red color vertex is the source vertex and the light-blue color vertex is destination, rest are either intermediate or discarded paths. 
 

This give four paths between source(A) and destination(E) vertex

Why this solution will not work for a graph which contains cycles? 

The Problem Associated with this is that now if one more edge is added between C and B, it would make a cycle (B -> D -> C -> B). And hence after every cycle through the loop, the length path will increase and that will be considered a different path, and there would be infinitely many paths because of the cycle
 

Follow the given steps to solve the problem:

• Create a recursive function that takes the index of a node of a graph and the destination index. Keep a global or a static variable count to store the count. 
• Keep a record of the nodes visited using a visited array and while returning mark the current node to be unvisited to discover other paths.
  • If the current node is the destination then increase the count.
  • Else for all the adjacent nodes, i.e. nodes that are accessible from the current node, call the recursive function with the index of the adjacent node and the destination.
• Print the Count as the required answer.

Below is the implementation of the above approach.

Time Complexity: The time complexity of this program is O(2^n), where n is the number of vertices in the graph. This is because in the worst case scenario, the program will have to recursively visit all possible paths from the source to the destination, which can be exponential in the number of vertices.
Auxiliary Space: O(N). Auxiliary stack space used by recursion calls

Last Updated :
14 Feb, 2023

Like Article

Save Article

Решение задачи

Перебор всех возможных путей

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

Функция принимает граф в виде списка смежности, начальную вершину и конечную вершину .

countPaths(g, v, t)
    if v == t
        return 1
    else
        s = 0
        for to in g[v]
            s += countPaths(g, to, t)
        return s

Время работы данного алгоритма в худшем случае , где — число путей в графе из в . Например, на следующем графе данный алгоритм будет иметь время работы . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до .

Метод динамического программирования

Пусть — число путей от вершины до вершины .
Тогда зависит только от вершин, ребра из которых входят в . Тогда таких , что есть ребро из в . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что . Это позволяет решить задачу методом динамического программирования.

Псевдокод

Пусть — стартовая вершина, а — конечная, для нее и посчитаем ответ. Будем поддерживать массив , где — число путей из вершины до вершины и массив , где , если ответ для вершины уже посчитан, и в противном случае. Изначально для всех вершин , кроме , а . Функция будет возвращать ответ для вершины . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива будут вычисляться по мере необходимости и не будут считаться лишний раз:

count(g, v)
    if w[v]
        return d[v]
    else
        sum = 0
        w[v] = true
        for c in g[v]
            sum += count(g, c)
        d[v] = sum
        return sum

countPaths(g, s, t)
    d[s] = 1
    w[s] = true
    answer = count(t)
    return answer

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

Пример работы

Рассмотрим пример работы алгоритма на следующем графе:

Изначально массивы и инициализированы следующим образом:

Сначала функция будет вызвана от вершины . Ответ для нее еще не посчитан (), следовательно будет вызвана от вершин и . Для вершины ответ также не посчитан (), следовательно будет вызвана уже для вершин и . А вот для них ответ мы уже можем узнать: для он равен , так как это — единственная вершина, ребро из которой входит в нее. Непосредственно для ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

Теперь мы знаем значения для вершин и , что позволяет вычислить . Также обновим значения в массиве : .

В самом начале для вычисления нам требовались значения и . Теперь нам известно значение , поэтому проследим за тем, как будет вычисляться . , но , следовательно значения и мы уже знаем, и нам необходимо вызвать . Ответ для этой вершины равен , так как это единственная вершина, ребро из которой входит в . Обновим соответствующие значения массивов и :

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины . :

Наконец, вычислим и обновим таблицы и :

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

См. также

• Динамическое программирование
• Кратчайший путь в ациклическом графе
• Задача о расстановке знаков в выражении
• Задача о порядке перемножения матриц

Источники информации

• Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..