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

Вычислить количество путей в графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.65
Котя Бонифаций
0 / 0 / 0
Регистрация: 23.10.2012
Сообщений: 3
05.09.2013, 19:31     Вычислить количество путей в графе #1
Дан граф.
Вычислить количество различных вариантов прохождения от одной точки до другой.
Пример:
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Ответ: 13

Решение приблизительно так:
Нарисуем путь из пункта А в Л. Начнем с конца, с пункта Л. К нему ведут дороги из И, Ж, К
В пункт И ведет дорога из Д. В пункт Ж ведут дороги из Д, В, Е. В пункт К ведет дорога из Е.
В пункт Д ведут дороги из Б и В. В пункт В ведут дороги из Б, А, Г. В пункт Е ведет дорога из Г.
В пункт Б ведет дорога из А. В пункт В ведут дороги из Б, А, Г. В пункт Г ведет дорога из А.
В пункт Б ведет дорога из А. В пункт Г ведет дорога из А.
Посчитаем, сколько "А" получилось. Из каждой "А" идет свой маршрут.
Миниатюры
Вычислить количество путей в графе   Вычислить количество путей в графе  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.09.2013, 19:31     Вычислить количество путей в графе
Посмотрите здесь:

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). C++
C++ Обход всех путей в графе
C++ Прогрмма по поиску кратчайших путей в графе
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск всех различных путей в графе C++
C++ Вычислить количество различных путей между всеми парами вершин графа
C++ Поиск кратчайших путей в графе
C++ Задача поиска множественных путей в графе

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

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

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