С вашими ограничениями подойдет решение полным перебором.
Сначала алгоритмом
Флойда ищем все кратчайшие расстояния между выбранными вершинами.
Потом перебираем все последовательности обхода и считаем минимум. Таких последовательность будет 10! = 3,6 * 10^6 даже на самом простом компьютере должно перебираться не более секунды.