Форум программистов, компьютерный форум CyberForum.ru

Поиск всех путей из одной вершины в другую в неориентированном графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
nymphaea
 Аватар для nymphaea
7 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 97
Записей в блоге: 2
15.03.2014, 23:24     Поиск всех путей из одной вершины в другую в неориентированном графе #1
Здравствуйте, участники форума!
Срочно необходима ваша помощь!
Требуется написать программу, которая будет искать все пути из заданной стартовой вершины в финишную. При этом, для каждого пути она должна считать кол-во пройденных рёбер. Ходить туда-сюда по одному и тому же ребру можно неограниченное количество раз, так как граф неориентированный.
Подскажите хотя бы идею, так как даже не представляю, как к этому подступиться.
У меня есть метод, который по заданной матрице смежности умеет отвечать на вопрос о существовании пути из одной вершины в другую.
Алгоритмы обхода в ширину/глубину не подходят, так как они не ставят перед собой цели рассмотреть все пути, а только проходят все рёбра. Что делать?
Программа должна быть на С/С++.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2014, 23:24     Поиск всех путей из одной вершины в другую в неориентированном графе
Посмотрите здесь:

Поиск всех циклов в неориентированном графе. C++
C++ Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе
Нахождение всех возможных путей для спуска с вершины матрицы C++
C++ Обход всех путей в графе
C++ В неориентированном графе посчитать количество компонент связности
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск всех различных путей в графе C++
C++ Поиск кратчайших путей в графе

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 20:41. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru