When actually finding the path, you can use http://en.wikipedia.org/wiki/Dijkstra's_algorithm
The edge length can be whatever metrics you want, such as cost or distance.
If routes never change, I would have all of the routes calculated. The number of paths between cities is only n^2 where n is the number of cities. if all of the paths are bidirectional then the amount of paths is cut in half. If you look at the numbers it isn't too bad for values in the hundreds or less. Lets look at a lookup table with 200 cities. The number of routes is 200x200 or 40,000. If each route takes on average n/2 hops between cities, which is the worst case if all cities were in a straight line and each step in the route takes two bytes to store, that is about 200 bytes per route. So the total amount of memory used to store all routes between the 200 cities is 40,000 routes * 200 bytes per route would be about 8 megabytes. 8 megabytes is easily manageable,
If you budget around 2 gigabytes to storing the table, you can store up to 1,200 cities still using the worse case of n/2 average hops per route. If the average number of hops is 10, you can store all of the routes between 14,000 cities in 2gb. A database of this size could fit in ram, however as this database gets larger you would want to store the database on the disk and cache frequently used routes in ram