I've never tried this but here's some ideas I have:
You'll need to keep track of all cities, so you will need a
You also need to know the distance between two cities that are directly connected to each other, so you will need a
cities_distances table like this:
This will let you keep track of how much distance it is from one city to another. Note that this is directional - The distance from A to B might not be the same as from B to A if the highway between them has a lane for each direction, and one lane has a detour around some natural feature (like a small lake, or difficult parts of terrain). Within a city, this is also important because you'll have one-way streets.
If you don't care about the direction of the distance between the two cities, you can just rename those two columsn
As for writing a query that gets the distance between any two cities, it might be easier to do that in code using Dijkstra's algorithm (because this is really just a graphing problem) than in query, but it might be possible using recursive queries. Or, you could generate a pre-calculated table that stores all this information and just look the data up in that.