1

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

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

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

1 4
1 2
1 3
2 4
3 4

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


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

2

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

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

3

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

Спасибо)

4

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

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

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

5

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

ivank пишет:

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

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

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

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

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

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

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

7

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

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

8

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

Fdg пишет:

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

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

9

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

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

10

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).