# Calculating shortest paths from all points in one layer to any points in another via road layer in QGIS?

I'm trying to calculate the shortest paths from all the points in a layer representing population settlements (the green points) to any of the points in another layer representing the hospitals (orange points), going through the roads in blue.

The idea is to see where are the gaps in terms of public service delivery (here for health facilities). I've tried using GRASS, converted all the vector layers into graph vertexes and connected my points to the road network using the "v.net" tool but couldn't manage to go further with GRASS tools.

Having checked a number of other subjects on StackExchange, it seems to me I could be using pgRouting or Dijkstra’s algorithm, but it seems to me that those two tools only allow to find the shortest paths to definite destination. As I'm just beginning on QGIS - or Python for that matter - I could be mistaken, but I don't want to waste too much time learning a tool that wouldn't do the job in the end.

A closest facility tool apparently exists in ArcGIS, so I guess I would need something equivalent in QGIS.

Could you please guide me to the best tools to do this?

• pgRouting can certainly do this; it's ultimately as flexible as you can make SQL queries, and is very powerful. Are you willing to go down the PostGIS route or do you just want to remain within QGIS? Nov 4, 2015 at 9:09
• My only requirement is to be able to post-analyse the data I get from pgRouting, directly using QGIS or in Excel for example. I don't know what are the pros and cons of using PostGIS in the process, but willing to use it if it makes things possible and not too technically challenging. Nov 4, 2015 at 11:56
• So here is where I am right now: I've used pgRouting to try to find shortest paths between points of the network; to do so, I've added "Source" and "Target" columns and used pgr_createTopology function to make the vector table routable, then used pgr_dijkstra to find shortest path between any pair of points in the network, but the request only works for a limited number of pairs, whereas all the roads in my network are connected. It seems that the topology of my network is not well defined but I don't know where could the problem be Nov 9, 2015 at 11:44
• Here is a dropbox link to the data I have, in a QGIS project file dropbox.com/s/n8ra8y7g25e1x40/… Nov 9, 2015 at 13:04
• Trying to open this but it crashes QGIS for me. A project file is only a set of references to your data, so it isn't enough anyway. E.g. `<datasource>../../../Student/asthecrowflies_stl_bphs_hub_lines2.shp</datasource>` refers to a location on your computer, but not on anyone else's. Have you ensured that all your source and target locations have equivalent locations that are located on the network edges? Nov 9, 2015 at 17:14

Looking at pgRouting tutorials, I thought the pgr_createTopology was enough to create source and target locations. I'm not sure to understand how to verify that the source and target locations have equivalent locations that are located on the network edges

I think my problem was that all of the crossroads where not mapped as nodes, so I used the v.split tool in GRASS to update my network, and the pgr_dijkstra request works now. Now do you know how I could assign to all of the points in my layers there corresponding number as "source" or "target" in my road network?

So after splitting your intersecting lines so that intersections are now points in your graph, the only remaining preparation task is to map your source and target points of interest to their nearest nodes in the graph so they can be routed between. The pgRouting docs have a useful but somewhat advanced example here, including this snippet of a plpgsql function:

``````-- Find nearest node
EXECUTE 'SELECT id::integer FROM ways_vertices_pgr
ORDER BY the_geom <-> ST_GeometryFromText(''POINT('
|| x1 || ' ' || y1 || ')'',4326) LIMIT 1' INTO rec;
source := rec.id;
``````

Then there is this example plpgsql function:

``````CREATE OR REPLACE FUNCTION get_nearest_station
(IN x_long double precision, IN y_lat double precision) -- input parameters
RETURNS TABLE -- structure of output
(
station_id integer,
city_name character varying,
station_name character varying,
dist integer -- distance to the nearest station
) AS \$\$

BEGIN

RETURN QUERY

SELECT id, city, station,
CAST
(st_distance_sphere(geom, st_setsrid(st_makepoint(x_long,y_lat),4326)) AS INT)
AS d
FROM stations
ORDER BY geom <-> st_setsrid(st_makepoint(x_long, y_lat), 4326)
LIMIT 1;

-- geometric operator <-> means "distance between"

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

The key part is the `ORDER BY geom <-> st_setsrid(st_makepoint(x_long, y_lat), 4326) LIMIT 1`, a pattern that is in both solutions.

You can use this with the following query (but you will have to adjust the above function slightly to match your schema):

``````SELECT get_nearest_station(ST_X(geom), ST_Y(geom)) FROM table;
``````

Finally, you can also work with `ST_ClosestPoint` between two point layers.

• Thanks a lot for the help. Just one more thing that might seem basic compared to the above, but if I understand well, I need to first get the x and y coordinates of my source and target points. I thought `ALTER TABLE public.balkh_road_network_complete_1_v_split ADD source_x numeric; UPDATE public.balkh_road_network_complete_1_v_split SET source_x = ST_X(ST_startpoint(geom));` would do the job but it's returning a blank column, any idea what I'm doing wrong? (and if this is the right way to get my target and source x,y coordinates?) Nov 12, 2015 at 12:28
• You don't need to get the x and y coordinates of those points. You need to take the locations of the places you want to route between, and get the `node_id` of the nearest source and target points from your network table. Nov 12, 2015 at 19:32