viv,

Была когда-то похожая тема - об определении дальности рейса между заданными городами.

При обсуждении одно направление мысли ушло в географию - хранить координаты, и вычислять расстояние геометрически.

В принципе, при должном владении приемами геометрии на сфере, получатся достаточно точные результаты -
дальность и азимут, которые можно будет использовать для обстрела одного заданного города из другого
с помощью дальнобойных орудий или баллистических ракет. Но с транспортными затратами это связано слабо.

Другое направление мысли - хранить таблицу элементарных расстояний между соседними пунктами,
а для вычисления дальних рейсов - суммировать эти отрезки.

Математически опять же получится правильно, но на практике сводится к решению каждый раз "задачи коммивояжера",
которая, как известно, аналитически не решается, а только комбинаторно, а потому вряд ли применимо.

Как крайний вариант - предлагали хранить расстояния вообще между всеми узлами, во всех нужных комбинациях.
Если количество узлов не вылезает за разумные пределы - вполне работоспособный вариант.

Для более крупных решений, компромисс, если не ошибаюсь, нашли в том, чтобы расширить таблицу расстояний,
и хранить расстояния не только между соседними пунктами, но и между другими крупными узлами,
а алгоритм научить сначала искать "магистральный" путь до ближайшего крупного узла, а потом от него - уже в уездный город N.