Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск минимального пути в ор графе, минимальный по количеству вершин 
:(
    Опции темы
coach
Дата 16.3.2007, 16:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 18
Регистрация: 28.8.2006

Репутация: нет
Всего: нет
Есть ли какой нибудь алгоритм, который выдает минимальный путь с минимальным  КОЛИЧЕСТВОМ вершин в ориентированном графе. 
PM MAIL   Вверх
Tectoder
Дата 16.3.2007, 16:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 202
Регистрация: 13.3.2007

Репутация: нет
Всего: 8
coach, чем не подходит метод Дейкстры, в котором длина каждого ребра положена равной одному?

Это сообщение отредактировал(а) Tectoder - 16.3.2007, 16:17
PM   Вверх
Earnest
Дата 19.3.2007, 14:45 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
При равных весах достаточно простого поиска в ширину, вычисляющего длину пути до каждого узла.


--------------------
...
PM   Вверх
pablo
Дата 19.3.2007, 17:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 320
Регистрация: 12.2.2005
Где: Вильнюс, Литва

Репутация: 4
Всего: 6
Цитата(coach @  16.3.2007,  16:15 Найти цитируемый пост)
Есть ли какой нибудь алгоритм, который выдает минимальный путь с минимальным  КОЛИЧЕСТВОМ вершин в ориентированном графе.  


Всё зависит от того, какие условия поиска. Если есть неотрицательные веса, то можно применить Алгоритм Дейкстры, если веса все равны то можно и простый поиском в ширину. Если есть отрицательные веса, то тогда надо применять алгоритм Белмана - Форда. Если же надо найти все пути от каждой вершины к каждой, то можно применить Алгоритм Флойда-Варшала. 

Так что всё зависит от критериев поиска.



--------------------
Первый блин всегда похож на сферу, иногда бывает и куб.
PM MAIL ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0470 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.