[GIS] How to apply Dijkstra’s algorithm in Python with PostGIS data

openstreetmaposm2popostgispythonrouting

I have currently parsed OSM data, from a PBF file, into a pgRouting database with the use of osm2po, an excellent parsing tool. I don't however want to use the algorithms provided by pgRouting and instead want to have a custom algorithm. But to start off and gain an understanding of how to use the data, I'll attempt to simply apply Dijkstra's algorithm.

My logic so far is to:

  1. Determine whether two points are within x distance.
  2. Get the two nodes closest to each point.
  3. Query the database with a bounding box.

The query to the database will return all nodes, including their: x and y position, target nodes, edge length (km) and the_geom, within the specified bounding box.

The difficulty I have now is, how can I use the data and apply Dijkstra's algorithm such as the algorithm here: http://thomas.pelletier.im/2010/02/dijkstras-algorithm-python-implementation/, as the query won't produce a graph like:

...      graph = {
...     'A': {'B': 10, 'D': 4, 'F': 10},
...     'B': {'E': 5, 'J': 10, 'I': 17},
...     'C': {'A': 4, 'D': 10, 'E': 16},
...     'D': {'F': 12, 'G': 21},
...     'E': {'G': 4},
...     'F': {'H': 3},
...     'G': {'J': 3},
...     'H': {'G': 3, 'J': 5},
...     'I': {},
...     'J': {'I': 8},
...     }

If Dijkstra's algorithm is not suitable for this, what routing algorithm is?

In addition to that, I'm slightly confused how routing algorithms work on parsed data, which has been parsed by any osm parser. From all the parsers I've come across, a node only ever has one target node. Wouldn't this mean that I could only ever move in one direction, that being to the target node, then the next target node and so on?

Thanks to anyone willing to improve my logic.

Best Answer

What you need is a directed graph. The table osm2po creates for pgRouting is not directed. Nevertheless you can derive one forward and one backward edge from each segment (table-row). The result is an adjacency list - a little different from your representation:

graph = {
  'A': {'B': 10, 'D': 4, 'F': 10},
}

osm2po (and I think pgRouting does also) uses this layout:

'A', 10 , 'B'
'A',  4 , 'D'
'A', 10 , 'F'
Related Question