Vi dos posibles soluciones.
Primero:
Para cada ciudad almacenar en la base de datos su latitud y longitud; cuando el usuario recibe una consulta, calcula la distancia con cualquier otra ciudad y devuelve resultados.
Pro es que puede agregar cada ciudad en db sin necesidad de agregar otra información.
Aquí
también puede encontrar fórmulas, ejemplos y código para el cálculo de la distancia de latitud-longitud...
Segundo:
Cree una tabla cities_dist con tres campos:city1_id, city2_id, distance y coloque todas las combinaciones posibles entre sus ciudades. Con eso, puede escribir una consulta con la ciudad seleccionada, siendo city1_id o city2_id.
Pro es que puede usar una consulta simple sin ningún cálculo, mientras que las desventajas son que debe completar esta tabla cada vez que inserte una nueva ciudad en su base de datos.
EDITADO después del comentario del usuario:
Imagina que tienes tres ciudades
ID NAME
1 New York
2 Rome
3 Berlin
Esa mesa debería verse como
CITY1 CITY2 DIST
1 2 1500
1 3 1200
2 3 400
Cuando el usuario quiera volar desde Berlín, puede 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
