Как посчитать количество путей в графе
Перейти к содержимому

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

  • автор:

Задача о числе путей в ациклическом графе

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

Функция [math]\mathrm[/math] принимает граф [math]g[/math] в виде списка смежности, начальную вершину [math]s[/math] и конечную вершину [math]t[/math] .

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

Время работы данного алгоритма в худшем случае [math]O(Ans)[/math] , где [math]Ans[/math] — число путей в графе из [math]s[/math] в [math]t[/math] . Например, на следующем графе данный алгоритм будет иметь время работы [math]O(2^)[/math] . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до [math]O(n)[/math] .

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

Пусть [math]P(v)[/math] — число путей от вершины [math] s [/math] до вершины [math] v [/math] . Тогда [math]P(v)[/math] зависит только от вершин, ребра из которых входят в [math]v[/math] . Тогда [math]P(v) = \sum\limits_P(c)[/math] таких [math]c[/math] , что есть ребро из [math]c[/math] в [math]v[/math] . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что [math]P(s) = 1[/math] . Это позволяет решить задачу методом динамического программирования.

Псевдокод

Пусть [math]s[/math] — стартовая вершина, а [math]t[/math] — конечная, для нее и посчитаем ответ. Будем поддерживать массив [math]d[/math] , где [math]d[v][/math] — число путей из вершины [math] s [/math] до вершины [math]v[/math] и массив [math]w[/math] , где [math]w[v] = true[/math] , если ответ для вершины [math]v[/math] уже посчитан, и [math]w[v] = false[/math] в противном случае. Изначально [math]w[i] = false[/math] для всех вершин [math]i[/math] , кроме [math]s[/math] , а [math]d[s] = 1[/math] . Функция [math]\mathrm[/math] будет возвращать ответ для вершины [math]v[/math] . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива [math]d[/math] будут вычисляться по мере необходимости и не будут считаться лишний раз:

[math] count(v) = \left \< \begin d[v], & w[v]=true \\ \sum\limits_count(c), & w[v]=false \end \right. [/math]

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

Значение функции [math]\mathrm[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\[/math] . Всего таких ребер для всех вершин в графе [math]O(E)[/math] , следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math] , где [math]V[/math] — число вершин графа, [math]E[/math] — число ребер.

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

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

Count-path-graph-example.png

Изначально массивы [math]d[/math] и [math]w[/math] инициализированы следующим образом:

вершина S 1 2 3 4 T
w true false false false false false
d 1 0 0 0 0 0

Сначала функция [math]\mathrm[/math] будет вызвана от вершины [math]T[/math] . Ответ для нее еще не посчитан ( [math]w[T] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана от вершин [math]3[/math] и [math]4[/math] . Для вершины [math]3[/math] ответ также не посчитан ( [math]w[3] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана уже для вершин [math]2[/math] и [math]S[/math] . А вот для них ответ мы уже можем узнать: для [math]2[/math] он равен [math]d[S][/math] , так как это [math]S[/math] — единственная вершина, ребро из которой входит в нее. Непосредственно для [math]S[/math] ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

вершина S 1 2 3 4 T
w true false true false false false
d 1 0 1 0 0 0

Теперь мы знаем значения для вершин [math]2[/math] и [math]S[/math] , что позволяет вычислить [math]d[3] = d[2] + d[S] = 2[/math] . Также обновим значения в массиве [math]w[/math] : [math]w[3] = true[/math] .

вершина S 1 2 3 4 T
w true false true true false false
d 1 0 1 2 0 0

В самом начале для вычисления [math]d[T][/math] нам требовались значения [math]d[3][/math] и [math]d[4][/math] . Теперь нам известно значение [math]d[3][/math] , поэтому проследим за тем, как будет вычисляться [math]d[4][/math] . [math]\mathrm[/math] , но [math]w[3] = true, w[2] = true[/math] , следовательно значения [math]d[3][/math] и [math]d[2][/math] мы уже знаем, и нам необходимо вызвать [math]\mathrm[/math] . Ответ для этой вершины равен [math]d[S][/math] , так как это единственная вершина, ребро из которой входит в [math]1[/math] . Обновим соответствующие значения массивов [math]d[/math] и [math]w[/math] :

вершина S 1 2 3 4 T
w true true true true false false
d 1 1 1 2 0 0

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины [math]4[/math] . [math]d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4[/math] :

вершина S 1 2 3 4 T
w true true true true true false
d 1 1 1 2 4 0

Наконец, вычислим [math]d[T] = d[3] + d[4] = 2 + 4 = 6[/math] и обновим таблицы [math]d[/math] и [math]w[/math] :

вершина S 1 2 3 4 T
w true true true true true true
d 1 1 1 2 4 6

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

См. также

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

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

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

Задача о числе путей в ациклическом графе

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

Функция [math]\mathrm[/math] принимает граф [math]g[/math] в виде списка смежности, начальную вершину [math]s[/math] и конечную вершину [math]t[/math] .

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

Время работы данного алгоритма в худшем случае [math]O(Ans)[/math] , где [math]Ans[/math] — число путей в графе из [math]s[/math] в [math]t[/math] . Например, на следующем графе данный алгоритм будет иметь время работы [math]O(2^)[/math] . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до [math]O(n)[/math] .

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

Пусть [math]P(v)[/math] — число путей от вершины [math] s [/math] до вершины [math] v [/math] . Тогда [math]P(v)[/math] зависит только от вершин, ребра из которых входят в [math]v[/math] . Тогда [math]P(v) = \sum\limits_P(c)[/math] таких [math]c[/math] , что есть ребро из [math]c[/math] в [math]v[/math] . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что [math]P(s) = 1[/math] . Это позволяет решить задачу методом динамического программирования.

Псевдокод

Пусть [math]s[/math] — стартовая вершина, а [math]t[/math] — конечная, для нее и посчитаем ответ. Будем поддерживать массив [math]d[/math] , где [math]d[v][/math] — число путей из вершины [math] s [/math] до вершины [math]v[/math] и массив [math]w[/math] , где [math]w[v] = true[/math] , если ответ для вершины [math]v[/math] уже посчитан, и [math]w[v] = false[/math] в противном случае. Изначально [math]w[i] = false[/math] для всех вершин [math]i[/math] , кроме [math]s[/math] , а [math]d[s] = 1[/math] . Функция [math]\mathrm[/math] будет возвращать ответ для вершины [math]v[/math] . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива [math]d[/math] будут вычисляться по мере необходимости и не будут считаться лишний раз:

[math] count(v) = \left \< \begin d[v], & w[v]=true \\ \sum\limits_count(c), & w[v]=false \end \right. [/math]

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

Значение функции [math]\mathrm[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\[/math] . Всего таких ребер для всех вершин в графе [math]O(E)[/math] , следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math] , где [math]V[/math] — число вершин графа, [math]E[/math] — число ребер.

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

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

Count-path-graph-example.png

Изначально массивы [math]d[/math] и [math]w[/math] инициализированы следующим образом:

вершина S 1 2 3 4 T
w true false false false false false
d 1 0 0 0 0 0

Сначала функция [math]\mathrm[/math] будет вызвана от вершины [math]T[/math] . Ответ для нее еще не посчитан ( [math]w[T] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана от вершин [math]3[/math] и [math]4[/math] . Для вершины [math]3[/math] ответ также не посчитан ( [math]w[3] = false[/math] ), следовательно [math]\mathrm[/math] будет вызвана уже для вершин [math]2[/math] и [math]S[/math] . А вот для них ответ мы уже можем узнать: для [math]2[/math] он равен [math]d[S][/math] , так как это [math]S[/math] — единственная вершина, ребро из которой входит в нее. Непосредственно для [math]S[/math] ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

вершина S 1 2 3 4 T
w true false true false false false
d 1 0 1 0 0 0

Теперь мы знаем значения для вершин [math]2[/math] и [math]S[/math] , что позволяет вычислить [math]d[3] = d[2] + d[S] = 2[/math] . Также обновим значения в массиве [math]w[/math] : [math]w[3] = true[/math] .

вершина S 1 2 3 4 T
w true false true true false false
d 1 0 1 2 0 0

В самом начале для вычисления [math]d[T][/math] нам требовались значения [math]d[3][/math] и [math]d[4][/math] . Теперь нам известно значение [math]d[3][/math] , поэтому проследим за тем, как будет вычисляться [math]d[4][/math] . [math]\mathrm[/math] , но [math]w[3] = true, w[2] = true[/math] , следовательно значения [math]d[3][/math] и [math]d[2][/math] мы уже знаем, и нам необходимо вызвать [math]\mathrm[/math] . Ответ для этой вершины равен [math]d[S][/math] , так как это единственная вершина, ребро из которой входит в [math]1[/math] . Обновим соответствующие значения массивов [math]d[/math] и [math]w[/math] :

вершина S 1 2 3 4 T
w true true true true false false
d 1 1 1 2 0 0

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины [math]4[/math] . [math]d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4[/math] :

вершина S 1 2 3 4 T
w true true true true true false
d 1 1 1 2 4 0

Наконец, вычислим [math]d[T] = d[3] + d[4] = 2 + 4 = 6[/math] и обновим таблицы [math]d[/math] и [math]w[/math] :

вершина S 1 2 3 4 T
w true true true true true true
d 1 1 1 2 4 6

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

См. также

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

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

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

Поиск количества путей в ориентированном графе

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город J?

Решать будем динамикой.

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

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Например, в города B и D можно прийти одним способом из города A. А в город С можно прийти из города B, города A или города C, поэтому количество различных путей в город С равно \( 1+1+1=3. \)

Итого получается, что в пункт J ведут 20 различных путей.

Задание 2 #14542

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, J, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город I?

Решать будем динамикой.

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

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт I ведут 27 различных путей.

Задание 3 #14541

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, G, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город F?

Решать будем динамикой.

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

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт F ведут 11 различных путей.

Задание 4 #14540

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город I?

Решать будем динамикой.

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

Итого получается, что в пункт I ведут 17 различных путей.

Задание 5 #14539

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город J?

Решать будем динамикой.

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

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт J ведут 8 различных путей.

Задание 6 #14536

На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, K, X, J, Q, P, L, M, O, N. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города A в город N?

Решать будем динамикой.

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

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Например, в город C можно прийти одним способом из города A, а в города B и D можно прийти одним способом из C. Тогда в город E можно прийти из города B, из города C или из города D, поэтому количество различных путей в город E равно \( 1+1+1=3. \)

Также заметим, что на графе присутствуют лишние дороги, не ведущие в город N, которые нам не нужны, и пути по которым считать не надо.

Итого получается, что в пункт N ведут 54 различных пути.

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

Дан ориентированный связанный граф без циклов.
Как найти количество различных путей от вершины s в вершину t? и вывести их(все пути).

например дан граф:
4 — вершины
5 — ребер

Пусть s = 1, а t = 4, тогда кол-во путей различных будет 3и, это:
1 — 2 — 4
1 — 4
1 — 3 — 4

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

2 Ответ от KADR 2009-10-18 13:17:54

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

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

3 Ответ от manof 2009-10-18 13:21:33

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

4 Ответ от ivank 2009-10-18 22:03:06

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

Если просто сосчитать — то динамическим программированием.

Если же вывести — то перебором. Не забывайте отсекать перебор, как только из текущей вершины нельзя попасть в конечную — тогда сложность перебора будет O(nk), где k = число путей (может быть экспоненциально большим)

5 Ответ от manof 2009-10-19 00:36:32

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

ivank пишет:

Если просто сосчитать — то динамическим программированием.

Если же вывести — то перебором. Не забывайте отсекать перебор, как только из текущей вершины нельзя попасть в конечную — тогда сложность перебора будет O(nk), где k = число путей (может быть экспоненциально большим)

А как ДП прикрутить для подсчета путей?

Вывод всех путей уже реализовал с помощью одного запуска DFS без пометок.

6 Ответ от ivank 2009-10-19 05:20:01 Отредактировано ivank (2009-10-19 05:20:31)

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

Ну, пусть f(u) = число путей из вершины u в t. Рекуррентное соотношение: f(u) = сумма f(v), по всем рёбрам (u, v) в графе. Всё будет хорошо, если граф ациклический.

7 Ответ от Fdg 2011-05-11 19:04:37

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

Как найти количество путей в ориентированном графе (к-во вершин <=50) от s до t длины не более k<=10?

8 Ответ от KADR 2011-05-11 21:16:32

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

Как найти количество путей в ориентированном графе (к-во вершин <=50) от s до t длины не более k<=10?

Динамикой по вершине и длине пути. Пусть f(i,j) — количество путей из вершины s в вершину i длины j. Тогда f(i,j)=сумма f(w,j-1) по всем w из которых есть ребро в i.

9 Ответ от Fdg 2011-05-11 21:27:25

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

А если нужно найти количество путей без циклов?

10 Ответ от KADR 2011-05-11 22:00:29

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

Ну, если тайм лимит не сильно маленький, то вроде бы можно так. Добавим ребро из t в t и теперь будем искать количество путей длины ровно k.

Пусть f(i,mask) это количество простых путей из s в i, в которых мы посетили только вершины из mask. Посчитаем эту динамику для всех путей длины k/2. Состояний должно быть не сильно много.

Посчитаем еще одну динамику g(i,mask) — количество простых путей из i в t, в которых мы посетили только вершины из mask. Опять же, посчитаем ее для путей длины k-k/2.

Теперь переберем центральную вершину v в пути длины k и нам надо для всех пар (mask1,mask2), которые имеют общий элемент только v посчитать сумму произведений f(v,mask1)*g(v,mask2). Для этого переберем v и mask1 и найдем сумму всех g(v,mask2), которые нам подходят.

Можно по включению-исключению: возьмем сумму всех g(v,mask2), отнимем сумму таких, которые имеют 1 общий элемент с mask1 (кроме v), затем прибавим те, которые имеют 2 и т.д. Для этого, разумеется, надо в начале сделать предподсчет по g(v,mask2).

Сообщений [ 10 ]

Страницы 1

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *