Re: Кратчайший маршрут

From

Oleg I. Khovayko ()

To

Victor Antropov

Date

2003-01-06T19:14:27Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Victor Antropov wrote:

> Как рекурсивно найти кратчайший путь в графе?

Рекурсивно - наверное, обойти граф весь и ставить
в каждый узел длину пути.

На самом деле, эта задача решается без всякой рекурсии

  *** Волновым алгоритмом. ***

Идея следуюшая: Из точки-источника пускаешь волну.
Как только волна достигла точки-приемника - путь найден.

Пример:

Есть граф:

1--2--3---4---5
   |          |
   6----------+--7

Надо найти путь между точками 1..7.
Из точки 1 пускаешь волну.
На шаге 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. Ошибка: Пути не существует.

> Нужно внятное описание алгоритма или исходники на Паскале.

Не, это сам пиши.

-- 
#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)