# How do I apply Dijkstra's algorithm in Python with PostGIS data?

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.

-

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'
``````
-
Thanks for helping, I posted the answer for those who may also need the help later. – John Bale Feb 15 '13 at 11:48

I have done it the way you are discussing, though I borrowed this algorithm instead of the one you're using.

I've also processed OSM to make it routeable and can vouch for osm2po. It does work well with Dijksra's algorithm and saves you a lot of time.

A* is an alternative. I believe it is implemented in PgRouting.

-
yes, pgRouting and osm2po provide A*, too. But playing around with it, you'll wonder: It's not always the fastest algo. It has an expensive calc-distance-overhead and when starting from border regions of your graph it is even slower than Dijkstra. – Carsten Feb 15 '13 at 7:33
I ended up using this algorithm, thanks. – John Bale Feb 15 '13 at 11:49

I actually figured out how to do this by myself. The first thing that confused me was how can one node only have one target node, hence can only go in one direction. The answer is it doesn't.

Firstly, in the database there can be multiple rows for a single source node, ie one for each edge going out from that node. Secondly, when you build a network using your data, the network will become directed, ie the target node of any edge will also be able to see the edge.

In Python, I easily created a network using the framework NetworkX, here: http://networkx.github.com/, via an algorithm I quickly made. NetworkX is well documented, so anyone should be able to build their own network.

Once you have built your network, you can call the method `to_dict_of_dicts` on it, which converts the network into a matrix, similar to the one I posted in my question. Now that you have a matrix to work with you can go ahead and implement any type of routing algorithm on it.

It took me a while to figure this out, but I hope this helps anyone who seeks to apply routing algorithms, on OSM parsed data, in the future.

UPDATE: "Any NetworkX graph behaves like a Python dictionary with nodes as primary keys" [source: http://www.cl.cam.ac.uk/~cm542/teaching/2011/stna-pdfs/stna-lecture11.pdf, pg 23]. You therefore do not need to convert the NetworkX graph into a matrix before performing your algorithm on it.

-
For your first step the "classical" layout is not needed. A Dijkstra does not need a reverse graph, meaning, the target does not necessarily need to "see" the edge and the corresponding source node. This "first idea" would make your graph smaller and more practical. Indeed, if you are going to climb the next level, namely bidirected routing, you actually need the reverse view. In addition: If I understand you correctly your are going to transform it to a matrix? Why? Think of how the data will be organized in memory or on disk and which consequences this or that approach might have. – Carsten Feb 15 '13 at 14:07
Thanks Carsten, you were right. The algorithm works without the need to convert the network into a matrix. – John Bale Feb 15 '13 at 15:25