Оптимальное решение для определения кратчайших расстояний

между пунктом А₁ и всеми остальными для модели (рис. 6.2)

Пункт	Вспомо- гатель- ные	Пункт
А1	А2	А3	А4	А5	А6	А7	А8
Строка Столбец	V1 = 0	V2 =11	V3 =17	V4 = 4	V5 =11	V6 = 8	V7 = 16	V8 = 15
А1	U1 =0
А2	U2 =11
А3	U3 =17
А4	U4 =4
А5	U5 =11
А6	U6 =8
А7	U7 =16
А8	U8 =15

Теперь можно определить индекс , а затем и :

Таким образом найдены все индексы и получен базовый вариант (табл. 6.4), для дальнейшего расчета кратчайших расстояний от пункта А ₁ до всех остальных. Приступаем к проверке оптимальности данного решения по правилу (6.10).

Проверяем каждую заполненную клетку табл. 6.4, сравнивая её В табл. 6.4 < , т. е. 7<12-4, следовательно, данное решение не является оптимальным.

Рассчитываем новый индекс υ ₂ по формуле (6): υ₂ = u₄+ l₄₂ = 4+7 = 11 и

u₂= υ₂=11. Проверка показывает, что и это решение не является оптимальным, поскольку l₅₃<υ₃-u₅ (6<18-11). Определив новый индекс u₃= υ₅₃=11+6=17 и индекс u₃= υ₃=17, получаем еще одно решение (табл. 6.5). Поскольку здесь соблюдается условие оптимальности (6.10), т. е. все расстояния меньше разности соответствующих им индексов, решение является оптимальным и, следовательно, кратчайшее расстояние от А₁ до всех остальных пунктов задано числами υ₂, υ₃, υ₄, υ₅, υ₆, υ₇ и υ₈, т.е. от А₁ до А₂ – 11 км, до А₃ – 17 км, до А₄ – 4 км, до А₅ – 11 км, до А₆ – 8 км, до А₇ – 16 км и до А₈ – 15 км.

Табл. 6.5 с оптимальным решением дает не только кратчайшие расстояния между А₁ и А_j пунктами, но и последовательность прохождения промежуточных пунктов, т. е. кратчайший маршрут. Пусть необходимо определить кратчайший маршрут из пункта А₁ в пункт А₇. Порядок работы следующий.

В столбце А₇, соответствующем конечному пункту маршрута, отыскиваем заполненную клетку, у которой расстояние равно разности индексов столбца и строки (lij = Vj - Ui). Такая клетка в рассматриваемом столбце всегда имеется (если таких клеток в столбце несколько, можно принять любую из них), в нашем примере – это А₅ А₇. Она обозначает последнее звено искомого маршрута – звено А₅ А₇. Для определения предпоследнего звена эта операция повторяется для пункта А₅, который является конечным для предпоследнего звена. В столбце А₅ расстояние равно разности индексов υ и u в клетке А₄А₅ (l₄₅ = υ₅ – u₄. т.е. 7=11-4). Таким образом, предпоследним звеном маршрута будет А₄ А₅. Повторив процесс для пункта А₄, находим звено А₁ А₄, предшествующее звену А₄ А₅. В результате кратчайший маршрут из пункта А₁ в пункт А₇ найден:

А_i→А₄→А₅→А₇.

Итак, мы определили кратчайшее расстояние от пункта А₁ до всех остальных пунктов А₂,А₃,…А₈. Проделав теперь показанные вычисления последовательно для каждого пункта А₂,А₃,…А₈, принимая последовательно u₂=0, затем u₃=0 и т. д., получим матрицу ║l_ij║ кратчайших расстояний по сети

Таблица 6.6