| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Нужен алгоритм поиска путей в графе...
C-D © (2003-02-23 17:50:00)
Путей вида A>B>C>A
Граф ориентированный. Задается матрицей смежности. Поиск по яндексу ничего не дал.
Sha (2003-02-23 23:12:00) [1]
Обнуляешь расстояния от т.А до каждой точки.
Пускаешь волну из точки А.
Получаешь список точек, куда можешь добраться за один переход и величину перехода (расстояние).
Обходишь список, пуская волну из каждой точки и вычисляя расстояние от т.А.
Получаешь список точек, куда можешь добраться за два перехода и расстояние.
Следи за циклическими путями - отсекай.
Повторяешь, пока не превысишь лимит (если надо найти путь меньше заданного) или сформированный список не пуст.
| |
