2.7. Общий алгоритм решения задачи маршрутизации на матрице орграфа

0. Задана матрица орграфа с весами на дугах, матрица стоимостей перехода ота_i к а_j.

1. Определяем начальную или конечную вершину. Тем самым определяется корень opt дерева.

2. Строим порядковую функцию от корня, преобразуя матрицу т.е. упорядочиваем вершины по уровнямЕ_i.

3. Строим opt дерево в соответствии с порядковой функцией, определяя оптимальные индексы для каждой вершины. На этом заканчивается I этап – условная оптимизация. При этом opt F_ц = I(a_n) при прямом ходе или opt F_ц = I(a₀) при обратном.

4. II этап – безусловная оптимизация. Решение находится противоположным ходом на opt дереве (по направлению к корню дерева). В результате получаем оптимальный путь в виде последовательности вершин с оптимальной суммой весов дуг:

– при прямом ходе = (а_n, а_n–1,…, а₁, а₀),

– при обратном ходе = (а₀, а₁,…, а_n–1, а_n).

Замечание. Если начальных (или конечных) вершин более одной, то вводится фиктивная вершина с дугами, имеющими нулевые веса, и задача сводится к рассмотренной.