30.6.2. Нахождение кратчайшего пути

Задача состоит в нахождении связанных между собой до­рог на транспортной сети, которые в совокупности имеют ми­нимальную длину от исходного пункта до пункта назначения.

Введем обозначения:

Dij — расстояние на сети между смежными узлами I и J;

Uj — кратчайшее расстояние между узлами I и J, U1 = 0.

Формула для вычисления Uj:

Из формулы следует, что кратчайшее расстояние Uj до уз­ла J можно вычислить лишь после того, как определено крат­чайшее расстояние до каждого предыдущего узла I, соединен­ного дугой с узлом J. Процедура завершается, когда получено Ui последнего звена.

Определить кратчайшее расстояние между узлами 1 и 7 (рис. 30.22).

Решение. Найдем минимальные расстояния:

Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут: 1-2-5-7.

< Предыдущая		Следующая >