Здравствуйте, watch-maker, Вы писали:

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

Да, действительно. Более того расстояния известны заранее и алгоритм Флойда–Уоршелла можно прогнать заранее, а в программе использовать уже готовые данные. Там правда много городов, порядка десятков тысяч, т.е. матрица будет порядка 1-2 гигабайта.