Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.06.2010, 16:25
гость

 
Сообщений: n/a

Поиск всех путей из начальной вершины орграфа в конечную
Помогите пожалуйста с алгоритмом. Дан ориентированный граф G. Нужно найти все пути из начальной вершины этого графа в конечную. Начальная и конечная вершины задаются произвольно.
  #2  
Старый 16.06.2010, 16:41
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Помогите пожалуйста с алгоритмом. Дан ориентированный граф G. Нужно найти все пути из начальной вершины этого графа в конечную. Начальная и конечная вершины задаются произвольно.
рекурсивный перебор.

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
поиск всех возможных путей из одной вершины, до другой Xavier Teodonius Графы 5 03.05.2009 16:01
Поиск путей в графе MrFandorin Графы 5 24.04.2008 01:25
Определение числа всех путей через заданные вершины Rusl_K Графы 1 28.01.2008 18:18
найти вершины орграфа гость Графы 2 28.12.2007 01:16