[pgrouting-users] Which method to use?

Stephen Woodbridge woodbri at swoodbridge.com
Mon Jan 30 17:44:21 EST 2012

On 1/30/2012 5:26 PM, Dave Potts wrote:
> Is there a generic introduction which list what each of the route method
> does and why I would what to use it with a given data set/

There is a tutorial
and here is my assessment:

Dijkstra solution:
This is a node based solution that converts a graph into a tree and the 
tree has all nodes that are reachable from the start node. This is used 
in the driving distance solution and has other applications where you 
might want the cost to get to multiple node. The default output is to 
only return that path from the start node to the destination node.

Astar search solution:
This is a modified Dijkstra solver that uses a Heuristic to direct the 
solver to the destination node. As a result, the graph solution is 
typically faster the Dijkstra because you only have to solve part of the 
graph needed to find the solution.

ShootingStar solution:
This is an edge based solver. IT IS CURRENT BROKEN! and as best as I can 
tell the last version that worked is v1.03. It is current running 
significantly (2-4x slower than the above two solutions). The reason it 
was created was because it support turn restrictions.

These are the main three solvers.

We just added a new branch TRSP (turn restricted shortest path) that is 
(will be) an alternative to ShootingStar. It is a modified Dijkstra 
solver, that takes turn restrictions and is only slight slower than 

In addition to these there is a TDSP (time dependent shortest path) that 
I believe is based off of Dijkstra solver, that allows costs to be 
dynamically selected based on a start time and time along the route, so 
if you have costs like average speed per time of day, the correct cost 
can be used when solving the problem.

And we have a couple more Google Summer of Code add-ons to pgrouting 
that I'm not sure I can do justice to explain.


More information about the Pgrouting-users mailing list