|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 06 Jan 2003 20:14:27
To : Victor Antropov
Subject : Re: Кратчайший маршрут
--------------------------------------------------------------------------------
Victor Antropov wrote:
> Как рекурсивно найти кратчайший путь в графе?
Рекурсивно - наверное, обойти граф весь и ставить
в каждый узел длину пути.
Hа самом деле, эта задача решается без всякой рекурсии
*** Волновым алгоритмом. ***
Идея следуюшая: Из точки-источника пускаешь волну.
Как только волна достигла точки-приемника - путь найден.
Пример:
Есть граф:
1--2--3---4---5
| |
6----------+--7
Hадо найти путь между точками 1..7.
Из точки 1 пускаешь волну.
Hа шаге 0 фронт волны находится в точке 1.
Далее:
Шаг: 1 Фронт: 2
Шаг: 2 Фронт: 3,6
Шаг: 3 Фронт: 4,5,7
Все, путь найден.
В каждом узле, куда пришел фронт, ставишь метку,
откуда он пришел, и по этим меткам раскручиваешь
обратный путь.
Реализовывать алгоритм надо через очередь.
То есть
1. Создаем очередь и засовываем в нее элемент 1
2. Пока очередь не пуста делать:
2.1. вынуть ссылку на элемент из очереди (тек)
2.2. Если тек. элемент - цель, выйти из цикла, и перейти на раскручивание
пути. Тек. элемент должен содержать ссылку на пред., и т.п - до самой
начальной точки. Это и будет кратчайший путь.
2.3. Иначе: для каждой граф-связи (дуги)
тек. элемента делать:
2.3.1. Заглянуть в узел, указаный связью (дугой)
2.3.2. Если узел не помечен (ссылка на prev пустая),
пометить его номером тек. узла, и положить
ссылку на указаный связь узел в очередь.
3. Ошибка: Пути не существует.
> Hужно внятное описание алгоритма или исходники на Паскале.
Hе, это сам пиши.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Кратчайший маршрут 
