 |
|
|
 
|
|
Поиск ВСЕХ путей на графе из А в Б 
| Гость_Дмитрий |
|
|||
|
Unregistered |
какие будут предложения по сабжу?
Желательно в виде последовательности конкретных шагов, а не в общем виде. Ещё раз обращу внимание, что мне нужен алгоритм поиска Всех маршрутов, а не кратчайшего. |
|||
|
||||
Загрузка ...
| ~FoX~ |
|
|||
 НЕ рыжий!!!  Профиль Группа: Участник Клуба Сообщений: 2819 Регистрация: 8.10.2003 Где: Зеленоград Репутация: 2 Всего: 68 |
Перебор
--------------------  …множественность никогда не следует полагать без необходимости… |
|||
|
||||
| poor_yorik |
|
|||
 Шустрый Профиль Группа: Участник Сообщений: 148 Регистрация: 12.1.2005 Где: Общаги г. Киева Репутация: 3 Всего: 8 |
Не могу подсказать, что делать с двумя вершинами, но есть задумки, если нужно найти количество путей между всеми парами вершин. Просматриваешь отдельно все ребра. Для ребра (i,j) просматриваем все пары вершин (k,l) . Если из k в і ведет x1 путей, а из J в l ведет x2 путей, то мы мы увеличиваем количество путей между k и l на x1*x2.
 --------------------
Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай... |
|||
|
||||
| Y-Vladimir |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 263 Регистрация: 16.7.2004 Где: Казань Репутация: 1 Всего: 6 |
А обход в ширину из вершины А не покатит?
|
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
Для поиска ВСЕХ путей поиск в ширину и есть полный перебор. Критерий отсечения - повторное посещение узла.
Впрочем условие этого (повторное посещение узла) не запрещает - тогда программа зависнет (если правильно кодить - просто зациклится)...  -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| poor_yorik |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 148 Регистрация: 12.1.2005 Где: Общаги г. Киева Репутация: 3 Всего: 8 |
Нет, я думаю что условие это запрещает. Вообще, я видел два варианта такой задачи. Нахождение узлов, которые не повтрояются либо по ребрам, либо по вершинам. То есть пути, у каждых которых все ребра или все вершины присутствуют не более одного раза. Переборный алгоритм напоминает поиск эйлеровых или гамильтоновых путей в графе.
--------------------
Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай... |
|||
|
||||
| yaja |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 98 Регистрация: 30.3.2005 Где: Санкт-Петербург Репутация: нет Всего: 1 |
Если въедешь, то тута написано - http://algolist.manual.ru/maths/graphs/shortpath/yen.php
|
|||
|
||||
| chaos |
|
|||
 Серийный программист Профиль Группа: Завсегдатай Сообщений: 2979 Регистрация: 7.7.2004 Где: Екатеринбург Репутация: нет Всего: 44 |
Может не в тему
 но если не много поправить эту программу http://forum.vingrad.ru/index.php?showtopi...&st=15&hl=chaos то получется желаемое решение  |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.1227 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |