Как решается задача о достижимости между всеми городами в графе с минимальными ограничениями на связность?

Возможно, имелась в виду задача о построении сети дорог минимальной стоимости, связывающей все города в графе, где города могут быть связаны не напрямую. 1 Для её решения используют, например, алгоритм Прима или Краскала: 1

• Алгоритм Прима: на каждом шаге присоединяют самую дешёвую нерассмотренную вершину к текущей «стройке». 1 Алгоритм заканчивают, когда присоединяют все вершины. 1
• Алгоритм Краскала: на каждом шаге строят дорогу минимальной стоимости, следя, чтобы не образовывались циклы. 1 Алгоритм заканчивают, когда из каждой вершины можно попасть в любую другую. 1

Ещё для решения подобных задач используют алгоритм Дейкстры, который позволяет для каждого из городов в графе построить кратчайшие пути до всех остальных городов. 2

Для оптимизации процесса можно сразу отвергать пути, которые превышают определённые ограничения, а не делать это после получения всех путей. 2