# pgrouting Dijkstra: routing with non-vertex data

I have some data samples, they are some traffic accident locations (have shape files) I really want to use the dijkstra function of pgrouting to look into their shortest distances between each other. However, I noticed that dijkstra requires all the points need to be the vertices of a topology. But obviously my data points are not the vertices of the road network.

Is there any way to integrate my data points to the road network and make them vertices too?

What is the good approach to route non-vertex data like this?

• Would it be enough to find the nearest vertex to your point and route from that? Or to find a point on the nearest segment? Otherwise if the point is not in the network, there is no route... Commented Jul 22, 2015 at 22:44
• Do you know your desired starting points in advance? If so, you could `ST_Split` your line features at those points in advance, and only then make your network routable. If you need to be more dynamic, you could split all of your segments into tolerably-small segments in advance and just take the nearest vertex when solving queries. Commented Jul 22, 2015 at 22:51
• @alpha-beta-soup . Thank you! I am sorry I just edited my question to be more clearer. But looks like you already understand the my problem very well. Commented Jul 22, 2015 at 22:58
• @RobSkelly Thank you! I am sorry I just edited my question to be more clearer. But looks like you already understand the my problem very well Commented Jul 22, 2015 at 22:58
• Since your data points indicate the positions of incidents on the road network, I think it makes the most sense to leave the network intact. (You say you don't need to, but re-dos are inevitable!) In general, accident data is something that changes frequently, and the road network isn't -- changes to the network will be destructive. Instead, you could locate a node and route from that, then optionally locate the nearest point on an edge, and subtract the proportion of the distance along that edge to the point. Commented Jul 22, 2015 at 23:36

If you are using pgRouting version 2.0.0 then you can use the Turn Restricted Shortest Path (pgr_trsp) algorithm which can use either the nodes of a network or (ideal for your scenario) the edges along with a percentage describing how far along the edge to start routing from.

pgRouting Turn Restricted Shortest Path Algorithm

The TRSP algorithm can also optionally take a turn restrictions table which would enable you to include things like banned turns.

In your case you can use the coordinates of your accident locations and derive a percentage along the closest edge using the PostGIS function ST_LineLocatePoint. There is a good overview of the use of this function in the documentation for OpenGeo suite.

Another option would be to connect your accident locations via GRASS GIS `v.net` function with `connect` option to your road network. You can either snap the points to the closest location on the road network, or let new edges be created.

Afterwards you would need to create new vertices from the roads network and assign each accident location to the closest vertice on the road network.

I wrote a more detailed answer on a similar question here. Nevertheless I think it would be benificial to do this in PostgreSQL with PostGIS (unless you are already using it), because you only have limited options with Plugins in QGIS.