Как точно называется задача для покрытия дорожной сетью?
Например есть такой неограф:
Вес дуг это расстояние между городами.
Применив минимальное остовное дерево получается такая картина:
Все вершины связаны в одну большую дорогу, но если перемещаться из Рязани в Казань(по остовному дереву), то потребуется 3+7+7+3=20 шагов.
То есть данный вид связи подходит для телефонной сети, но не для дорожной. А в идеале, должна быть еще дорога между Рязанью и Казанью.
То есть должны быть еще элементы оптимизации, где будет коэфицент зависимость стоимости прокладки дороги по отношению к времени перемещения из городов(как то так).Чем выше такой коэфицент тем больше дуг будет между вершинами.
Есть ли конкретная задача которая этим занимается?