 |
|
Модераторы: Daevaorn |
 
|
|
Поиск минимального пути в ор графе, минимальный по количеству вершин 
| coach |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 18 Регистрация: 28.8.2006 Репутация: нет Всего: нет |
Есть ли какой нибудь алгоритм, который выдает минимальный путь с минимальным КОЛИЧЕСТВОМ вершин в ориентированном графе.
|
|||
|
||||
Загрузка ...
| Tectoder |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 202 Регистрация: 13.3.2007 Репутация: нет Всего: 8 |
coach, чем не подходит метод Дейкстры, в котором длина каждого ребра положена равной одному?
Это сообщение отредактировал(а) Tectoder - 16.3.2007, 16:17 |
|||
|
||||
| Earnest |
|
|||
 Эксперт Профиль Группа: Экс. модератор Сообщений: 5962 Регистрация: 17.6.2005 Где: Рязань Репутация: 53 Всего: 183 |
При равных весах достаточно простого поиска в ширину, вычисляющего длину пути до каждого узла.
-------------------- ... |
|||
|
||||
| pablo |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 320 Регистрация: 12.2.2005 Где: Вильнюс, Литва Репутация: 4 Всего: 6 |
Всё зависит от того, какие условия поиска. Если есть неотрицательные веса, то можно применить Алгоритм Дейкстры, если веса все равны то можно и простый поиском в ширину. Если есть отрицательные веса, то тогда надо применять алгоритм Белмана - Форда. Если же надо найти все пути от каждой вершины к каждой, то можно применить Алгоритм Флойда-Варшала. Так что всё зависит от критериев поиска. -------------------- Первый блин всегда похож на сферу, иногда бывает и куб. |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0448 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |