| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Найти все возможные пути между 2 узлами графа |
| Автор: Empirik 23.12.2009, 15:15 |
| Доброго времени суток. На графе пытаюсь решить вот такую задачку. Есть граф (boost::adjacency_list), вершины в нем - это таблицы в субд, а ребра - это связи между ними. разумеется в нем есть циклы. Так вот нужно найти все пути от одной таблицы до другой. К примеру Есть таблицы: рабочий, отдел, инструмент. Рабочий ссылает на таблицу отдел и на таблицу инструмент, инструмент так же ссылается на таблицу отдел. Так вот вопрос, как найти не только самый кротчайший путь между рабочим и отделом, но и второй через инструмент? Ни как не могу подыскать подходящий алгоритм, помогите пожалуйста. |
| Автор: Earnest 23.12.2009, 18:29 |
| Да любой поиск, в глубину, например. Только нужно слегка модифицировать агента, или как он там называется. Чтобы как только происходит доступ к ребру, на другом конце которого конечная вершина, запоминаем где-нибудь текущий путь к ней (т.е. цепочку предшественников). |