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

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

Ну вроде пара гигабайт — это совсем не много, даже в память разом загрузить обычно можно. Вот со временем хуже. Но если алгоритм Флойда–Уоршелла предназначен для плотных графов, то для разреженных можно использовать более специфические реализации, например такие как алгоритм Джонсона, или даже просто запустить алгоритм A* несколько раз, если получится достать хорошую эвристику (если "города" в задаче соответствуют реальным городам из жизни, то как правило с этим нет проблем).

К сожалению, я не знаком с термином "k-близкий граф", поэтому не могу посоветовать как использовать это свойство.