Некоторые соображения имеются:
1. Расстояние между двумя пунктами при беспересадочном полете очевидно кратчайшее.
2. Посмотреть расстояния на сайтах типа expedia.com, webflyer.com, но там они все же отличаются друг от друга.
3. Перебрать разумные сочетания близлежащих к прямому маршруту пунктов. Определить суммарные расстояния для каждого такого комбинированного маршрута. Найти маршрут с наименьшим расстояние.
4. Проблема 1. При таком алгоритме всегда есть вероятность "не заметить" еще более кратчайший маршрут (неполная индукция), следовательно, результат носит вероятностный характер.
5. Проблема 2. В разное время года, а также дни недели искомые кратчайшие рейсы не будут выполняться, следовательно искомая величина кратчайшего маршрута станет зависеть от даты.
6. Вычисление расстояний по координатам GPS дадут другие результаты, т. к. самолеты летят по удобным для полетов маршрутам, а не только по кратчайшим.
Это только первоначальные выкладки и замечания.
Если у кого есть мысли на этот счет, поделитесь, пожалуйста, ими со мной, т. к. проблема эта очень важна для меня. Заранее спасибо.