# Calculating many shortest paths with pgRouting

I have 145013 Danish addresses, and 10 big cities in Denmark as points in QGIS. Furthermore, I have four vector layers that connect all the points. They are small roads, main roads, freeways and ferry routes. See the screen dump from QGIS below for an illustration:

Now I would like to calculate the shortest distance from each address to each of the 10 big cities. I will use pgRouting for this, and I have followed the tutorial on finding 1 shortest path at http://anitagraser.com/2013/07/06/pgrouting-2-0-for-windows-quick-guide/

However, I can't figure out how to extend the problem from 1 path to (145013 * 10 =) 1450130 paths.

What method should I use in pgRouting, and how do I incorporate all the 1450130 paths?

I use:

• QGIS 2.1.0
• postgres 9.2
• postgis 2.0
• pgRouting 2.0
• OS: Win 7 64bit

I have shared my data here: https://www.dropbox.com/sh/rn8gdxr1bki4q4x/fFRd0PerkP

It's in a QGIS project file.

## 2 Answers

You can use a new algorithm of pgRouting 2.0 nammed `pgr_kDijkstra`. It will allow you to request "1-n" shortest paths with a single query.

There are two variations: one returns the full path of all routes and one only returns the total cost for each route.

The documentation should explain how to use it: http://docs.pgrouting.org/2.0/en/src/kdijkstra/doc/index.html#pgr-kdijkstra

First load data into postgis and convert all data to same projection. Create one table from all data and follow PgRouting tutorial to create edges and vertexes. I really hope that that data is topologically correct already and you dont need to fix those issues. ( Have you considered just using osm2po data for your network ? )

If you have already done it, then see pgrouting dijkstra example and do:

This works but is slow. i used Finnish osm2po data for testing

``````CREATE OR REPLACE FUNCTION get_all_routes(target int) RETURNS VOID  AS
\$BODY\$
DECLARE
r record;

BEGIN

CREATE TABLE route_res as  SELECT  0 , route.*
FROM (SELECT  seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM vw_finland_routing',
10 , 60, false, false) ) as route  ;

FOR r IN
SELECT source from vw_finland_routing
LOOP

INSERT INTO route_res  SELECT  r.source , route.*
FROM (SELECT  seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM vw_finland_routing',
r.source  , target, false, false) ) as route ;

RAISE NOTICE  ' Running at % source id' ,r.source ;
END LOOP;

END
\$BODY\$
LANGUAGE plpgsql;
``````

AND

``````SELECT get_all_routes(10) -- where 10 is target from city
``````

Solution is slow and badly written. CREATE table needs to be taken out from function or needs to be in if exist block. to get some performance out of this you need to run N queries to target or if you can change it so that source is city and target is in for loop. My other ideas for problem are using `pgr_kDijkstra`. Or you can create city wide polygon and use it to overwrite that area source/target id's so function needs only find an area (takes 1000-> or more edges from route table)

• Thanks for the answer! I have imported all data into QGIS, and I have merged all the roads to 1 layer, but I'm unsure what to do with the addresses and big cities (start and end points of my paths). Should these layers be merged with the road layer and imported into a postgis table, or should I have 3 tables; one for the roads, one for the start points, and one for the end points?
– Mace
Oct 17, 2013 at 11:48
• you need to have "target" id:s in routes layer´? Have you used pgr_createTopology('<table>', float tolerance, '<geometry column', '<gid>') ? Oct 17, 2013 at 12:22
• but my targets are points and the roads are lines. I thought it wasn't possible to merge these to one layer.
– Mace
Oct 17, 2013 at 13:59
• Inspired by your idea and looking online I thought of using the following select to find the source ids:Select ST_Closestpoint(ST_Collect(a.geom), b.geom) as geom from roads a inner join addresses b on ST_Dwithin(a.geom, b.geom, 1000) group by b.id, b.geom; Wouldn't that do it?
– Mace
Oct 19, 2013 at 11:17
• Okay. I am using the following select to get the nearest road to each of the 10 cities: "SELECT DISTINCT ON(h.id) h.id as id_city, b.*into snap_cities FROM roads b INNER JOIN cities h ON ST_DWithin(h.geom, b.geom, 1000) ORDER BY h.id, ST_Distance(b.geom, h.geom);" And i will also use this select for the addresses, and then try to use ur function together with `pgr_kdjikstraCost()`
– Mace
Oct 21, 2013 at 12:43