Администрация Щелковского района в Московской области хочет обновить сеть дорог. Отремонтировать все дороги нет

Администрация Щелковского района в Московской области хочет обновить сеть дорог. Отремонтировать все дороги нет возможности, поэтому необходимо выбрать самое дешевое для ремонта подмножество дорог, которое обеспечит связность крупных населенных пунктов района между собой. В качестве вершин возьмите 8-10 крупнейших населенных пунктов района либо центры городских и сельских поселений района. В качестве меры стоимости ремонта возьмите длину дороги.

Сформулируем оптимизационную задачу:
Целевая функция общего пути участков стремится к минимуму:
fX=i=115Li*xi→min
Ограничением данной задачи является общая стоимость ремонта дороги, которая должна быть меньше Q - общего объёма ассигнований, выделяемых на ремонт дороги:
i=115q*Li≤Q,
Где q – затраты на ремонт 1 км дороги,
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15≥0,
x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15≤1,
Так как нам нужно фактически решить задачу поиска кратчайшего пути, представим данную задачу в виде графа. Пусть сеть дорог - это граф G=(V(G),E(G)),
где V(G) – множество вершин графа (населенные пункты района)
E(G) – множество рёбер графа (длина дороги между населенными пунктами)
Определим длины дорог между пунктами, воспользовавшись Яндекс-Картами, инструментом линейка (рис. 12):
Рисунок 12 - Карта Щёлковского района
Составим граф, в котором первым населенным пунктом будет «Фряново», а последним «Медвежьи озёра», а вес рёбер графа будет равен протяженности дорог (рис

. 13):
Рисунок 13 – Граф сети дорог Щёлковского района
Вручную посчитаем кратчайший путь из Фряново в Медвежьи озёра алгоритмом Дейкстры. Первый шаг это установка минимальной метки для населенного пункта Фряново – 0, а остальным поставим метку ∞ (рис. 14):
Рисунок 14 – Обозначения весов рёбер на 1 шаге.
На втором шаге рассчитываем метки «соседей» Фряново по очереди возрастания длины пути до Фряново, то есть начиная с Могутово (рис. 15):
Рисунок 15 – Обозначения весов рёбер на 2 шаге.
Могутово присваиваем метку 0+5.37=5.37. Это лепестковая вершина (не имеет продолжения), поэтому через нее не может быть кратчайшего пути и в рамках нашей задачи, а в случае нехватки финансирования эту вершину графа можно отбросить.
Огуднево присваиваем метку 0+13.6=13.6