Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 14. На рис. 3 представлен граф, имитирующий сеть дорог и показывающий стоимость перевозки единицы груза между отдельными пунктами.

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

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

d_ij расстояние на сети между смежными узлами i и j;

U_j кратчайшее расстояние между узлами i и j, U₁ = 0. Значение U_j рассчитывается по зависимости

Из формулы следует, что кратчайшее расстояние Uj до узла j можн...