2.4. Алгоритм решения задачи с помощью произвольного дерева маршрутов

0. Исходные данные: орграф [A, R] в графическом представлении с весами v(a_i, a_j) на дугах.

1. Определяем начальную и конечную вершины a₀ и a_n.

2. Строим произвольное дерево маршрутов с корнем в a₀ (прямым ходом):

а) организуем вектор вершин М и вектор дуг Д, начальную вершину a₀ заносим в М;

б) исходящие дуги (а₀, а_к) заносим в Д, а вершины а_k – в М;

в) для каждого а_k находим все исходящие дуги (а_k, а_е); если а_е М, то заносим ее в М, а дугу (а_k, а_е) – в Д; иначе переходим к новой а_е;

г) проверка: если М содержит не все вершины из А, то выбираем новую а_k и переходим к (в); иначе – КОНЕЦ.

3. Индексируем все вершины а_k построенного дерева, образуя вектор индексов I.

4. Строим opt дерево, улучшая индексы вершин:

а) дополнительно к Д организуем вектор дуг антидерева – АД;

б) включаем в дерево очередную дугу (a_i, a_j) антидерева и проверяем: если индекс a_j улучшился, то дугу (a_i, a_j) заносим в вектор Д вместо дуги (а_k, а_j), которую заносим в АД, и переходим к (3). Иначе – переходим к следующей дуге антидерева. И так далее, пока индекс хотя бы одной вершины можно улучшить.

В результате получаем:

1) индекс а_n есть длина opt пути: I(a_n) = opt |S(а₀, а_n)|;

2) путь S(а₀, а_n) однозначно определяется на построенном дереве обратным ходом.