Which is the best way to store roads for the shortest path finding application?

Question

I would like my application which is simply a shortest path finder in a city to meet the following requirements:

• the city roads network should be stored persistently on disk and loaded into memory on demand (to execute the shortest path finding algorithm);
• I would like to use something like OpenLayers to view the results that have been yielded by the shortest path algorithm;
• the 'OpenLayers view' should contain not only the results, but the map (uninteractive) of the city itself.

As for now I am thinking of the following architecture:

• PostGIS enabled database to store roads ('roads' table);
• PostGIS enabled database to store the actual map data to render it in OpenLayers;
• a table for the results of shortest path algorithm in the PostGIS enabled database (I would like to view a couple of shortest paths simultaneously);
• a web app with OpenLayers which shows the map from the 'map' table, shows the roads layer from the 'road' table and the shortest path from the 'shortest path' table.

Does this sound correct or should I change anything?

Answer 1

Underdark has a very good guide to shortest path with postgres+posdtgis+pgrouting (using QGIS to Visualise the data)

The aim of this post is to describe the steps necessary to calculate routes with pgRouting. In the end, we’ll visualize the results in QGIS.

This guide assumes that you have the following installed and running:

Postgres with PostGIS and pgAdmin
QGIS with PostGIS Manager and RT Sql Layer plugins

http://underdark.wordpress.com/2011/02/07/a-beginners-guide-to-pgrouting/

With Openlayers

This workshop has a guide to setting up pgrouting with openlayers

http://www.pgrouting.org/docs/ol-workshop/index.html

Answer 2

The shortest path will send you back a list of segments used to make your route and the cost. It means that each time you query the the shortest path your shortest path, you can join it to your road network using the identifiers the shortest path algorithm send you back. If the route are supposed to be shown dynamically, there is no use in saving the routing result in a table. Otherwise, indeed it makes sense. So basically you would need the tables:

1. The routing table whith also the fields required by pg_routing. When you get the results from PGRouting, you join it with your road table based on edge id.
2. The dataset related to your city

If you want to see different results, save them on the client side if the purpose is not to save them permanently. Otherwise, your option of saving the routing result is good.

So your architecture makes sense. Just keep the routing table being the same as you road table and use it for the routing. If you want to save all you routes results in the same time, find a way to give an identifier to each route so that you have something like that :

edge_id sequence_number route_id