Здравствуйте, Аноним, Вы писали:

А>Это же travelling salesman problem, не?
А>http://en.wikipedia.org/wiki/Travelling_Salesman_problem

Нет. Для решения этой задачи можно применить к графу алгоритм Флойда–Уоршелла. После чего по полученной матрице найти в лоб лучшую пару за O(N²). Соответственно, полная сложность решения будет равна сложности алгоритма Флойда–Уоршелла, то есть O(N³).