Eu vi duas soluções possíveis.
Primeiro:
Para cada cidade armazene no banco de dados sua latitude e longitude; quando o usuário recebe uma consulta, você calcula a distância com todas as outras cidades e retorna resultados.
Pro é que você pode adicionar todas as cidades em db sem a necessidade de adicionar outras informações.
Aqui você pode encontrar fórmulas, amostras e códigos também para cálculo de distância latitude-longitude ...
Segundo:
Criar uma tabela
cities_dist com três campos:city1_id, city2_id, distance e coloque dentro de cada combinação possível entre suas cidades. Com isso você pode escrever uma consulta com a cidade selecionada sendo city1_id ou city2_id.Pro é que você pode usar uma consulta simples sem nenhum cálculo, enquanto os contras são que você precisa preencher esta tabela sempre que você inserir uma nova cidade em seu banco de dados.
EDITADO após comentário do usuário:
Imagine que você tem três cidades
ID NAME
1 New York
2 Rome
3 Berlin
Essa mesa deve ficar assim
CITY1 CITY2 DIST
1 2 1500
1 3 1200
2 3 400
Quando o usuário quiser voar de Berlim, você pode usar
SELECT c1.name, c2.name, cd.dist
FROM cities_dist cd
INNER JOIN cities c1 ON cd.city1 = c1.id
INNER JOIN cities c2 ON cd.city2 = c2.id
WHERE cd.city1 = your_id
OR cd.city2 = your_id
ORDER BY cd.dist ASC
