Составить программу(решение задачи минимизации)

Описание задачи : Есть граф с минимум 10000 вершин(например любой город, у которого каждый перекресток это вершина графа), у него есть матрица расстояний(она считается идеальной), нужно заменять несколько самых ближайших друг к другу вершин на одну и следить за тем, чтобы выполнялось одно из двух условий(на свой выбор):
1)чтобы кол-во вершин после манипуляций было не больше определенного числа(выбирается самостоятельно)
2)чтобы общая ошибка расстояний была не больше какого то определенного числа(также самостоятельно)