графы - Все возможные пути

[manuk]

привет всем)))!!!
я студент 2 курса изучаю с++))), вот дошёл до графов))))!!
пока у меня очень плохо получается с ними(((((!!!
Препод дал задачку:

Лабиринт задается матрицей сложности N*N.где С(i,j)=1,если узел i связан с узлом j посредством дороги.Часть узлов назначается входами.часть выходами.Входы и выходы задаются последовательностями узлов X(1),...,X(p) и Y(1),..,Y(k) соответственно.
Найти максимальное число людей которых можно провести от входов до выходов т о чтобы:
1-их пути не пересекались по дорогам.но могут пересекаться по узлам
2-их пути не пересекались по узлам

объясните пожалуйста с чего начать хотя бы!!!
и если можете киньте пожалуста код, я буду разбираться в нём))!!!
а то никак я его не понимаю(((!!!

[Z1000000]

http://www.opita.net/node/481

Или в гугле набираешь точным поиском : "Все возможные пути"

[sabbathist]

Классическая задача на DFS (поиск в глубину). Называется "лабиринт с личными дверями"

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

[sabbathist]

Z1000000, там по ссылке для взвешенных графов, да еще и с возможными отрицательными весами. Штука полезная - но слишком "тяжеловесная" для данной задачи.

[Z1000000]

Сообщение от sabbathist

Называется "лабиринт с личными дверями"

Что это за задача? Гугл о ней не слышал. Можно ссылку?

[sabbathist]

Ну, условие у нее такое как в первом посте. А вот о том, насколько она классическая, вопрос спорный, наверное. В книгах по олимпиадам для школьников публиковалась.

[Z1000000]

А решается в лоб?
Полный обход в глубину для всех входящих дверей? И последующий просмотр всех найденных путей, и выбрасывание - не удовлетворяющих условиям.

[sabbathist]

Нашли 1 путь (кратчайший). Пометили. Потом ищем следующий (не пересекающийся с первым. Помечаем. И так далее.

[Z1000000]

Непонятно, почему 1 путь - кратчайший.
Твой алгоритм ( пост 3) находит первым не обязательно кратчайший путь.

[sabbathist]

Да. Про "кратчайший" я сдуру написал.