Calculating distance between 400 cities and optimi

Question

I've got a database of around 400 cities. User selects a city in which he lives, and enters the distance which he is willing to travel (for example, 40kilometers). The city_id is stored into search table, with some other irrelevant information. When user submits the form, he's redirected to results page, on which all results from search table are shown, that meet the criteria, but I want to order them by the distance between city form user's city and the result city, and order the results by that distance (closest first). How would I calculate the distance between the cities, and then order them? What tables would I have to add to each city, so I would actually calculate the distance, and is there any way I could just run a loop which would find the coordinates of each city and store them? My currenty cities table only has id, name and zip

Any help would be appreciated.

Answer 1

I saw two possible solutions.

First one:
For each city store in database its latitude and longitude; when user gets a query, you calculate distance with every other city and return results.
Pro is you can add every city in db without the need to add other info.
Here you can find formulas, samples and code too for latitude-longitude distance calc...

Second:
Create a table cities_dist with three fields: city1_id, city2_id, distance and put inside every possible combination among your cities. With that you can write a query whit selected city beeing city1_id or city2_id.
Pro is that you can use a simple query without any calc, while cons are that you have to fill this table anytime you insert a new city in your database.

EDITED after user comment:
Imagine you have three cities

ID  NAME
1   New York
2   Rome
3   Berlin

That table should look like

CITY1  CITY2  DIST
1      2      1500
1      3      1200
2      3       400

When user want to fly from Berlin you could use

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

Answer 2

Depending on how accurate the results should be it would be easiest to save latitude/longitude (geo coordinates) as extra columns to each city.

To get the distance just use Pythagoras (or some more accurate geo-formula that takes the surface of the earth into consideration):

distance = sqrt((city.x - my_x)^2 + (city.y - my_y)^2)

Put this into your WHERE clause and you will get the air-line distance.

There are more complicated ways to pre-calculate all distances, but for you this would be sufficient.