2.3. Идея решения задачи

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

Очевидно, что существует дерево, в котором все вершины имеют opt индексы. Такое дерево можно построить преобразованием любого исходного дерева для заданного графа с корнем в начальной или конечной вершине, испытывая поочередно все дуги исходного графа, не вошедшие в данное дерево.

Определение. Любой граф без циклов называется деревом.

Любое дерево обладает замечательным свойством: всякий путь на дереве определяется однозначно. Чтобы построить дерево для орграфа, нужно отвлечься от ориентации его дуг.

Дадим индуктивное определение индекса (по рекуррентной схеме). Положим, что на всех дугах (a_i, a_j) орграфа заданы веса v(a_i, a_j) и последовательность вершин а₀,…, а_n. Тогда при прямом ходе:

I(а₀) ≡ |S(а₀, а₀) ≡ 0,

I(а₁) ≡ |S(а₀, а₁) ≡ I(а₀) + v(a₀, a₁) = v(a₀, a₁),

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

I(a_i) ≡ |S(а₀, а_i) = I(a_i–1) + v(a_i–1, a_i),

i = 2,…, n;

при обратном ходе:

I(a_n) ≡ |S(а_n, а_n) ≡ 0,

I(a_n–1) ≡ |S(а_n–1, а_n) = I(a_n) + v(а_n–1, а_n) = v(а_n–1, а_n),

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

I(a_i) ≡ |S(a_i, a_n) = I(a_i+1) + v(a_i, a_i+1),

i = n – 2,…, 0.

Однако при реализации такой схемы необходимо потребовать выполнения следующего условия: подпуть оптимального пути есть путь оптимальный (это условие не работает, когда проявляется последействие, т.е. когда для I(a_i) нет выбора).