# How to calculate shortest path dynamically considering other shortest paths calculated in same run?

My topic is to minimize the cost of construction line digging. Starting from a source point I have several households that need to be connected to the that line. My plan was to calculate the shortest path for each source -> house and then cutout the overlapping lines.

In the example below I would then have a route on the Eastern street that goes from house 1-4, where the line for house 4, for instance, only reaches to house 3 and not the whole way to the source point (red) as I cutout its shortest path with the shortest pathes from houses 1 to 3. However, for house 5 the shortest path would have been the Western road, which is why it doesn't intersect with any other shortest path. But practically a connection from house 4 would have been more cost efficient. How can I include this consideration into my algorithm using PostGIS and pgrouting?

Lets make an approximation of the steiner-tree: Suppose that

• the sources are 1 & 10 the edges
• the houses are 2,3,4,5,6,7,8,9,11,12,13 (from the information of the sample data 14, 15, 16, & 17 are disconnected from the rest of the graph, those nodes need to be connected before considering them)
• Because visually all lengths look the same, let the edges weights the id number of the edge

Steps:

• The nearest house(2,3,4,5,6,7,8,9,11,12,13) to the sources(1,10) is `2` (using edge 1)
• The nearest house(3,4,5,6,7,8,9,11,12,13) to the sources(1,10,2) is `3` (using edge 2)
• The nearest house(4,5,6,7,8,9,11,12,13) to the sources(1,10,2,3) is `4` (using edge 3)
• The nearest house(5,6,7,8,9,11,12,13) to the sources(1,10,2,3,4) is `5` (using edge 4)
• The nearest house(6,7,8,9,11,12,13) to the sources(1,10,2,3,4,5) is `6` (using edge 5)
• The nearest house(7,8,9,11,12,13) to the sources(1,10,2,3,4,5,6) is `8` (using edge 7)
• The nearest house(7,9,11,12,13) to the sources(1,10,2,3,4,5,6,8) is `7` (using edge 6)
• The nearest house(9,11,12,13) to the sources(1,10,2,3,4,5,6,8,7) is `9` (using edge 9)
• The nearest house(11,12,13) to the sources(1,10,2,3,4,5,6,8,7,9) is `11` (using edge 11) So the resulting graph up to this point is edges(2,3,4,5,6,7,8,9,11)
• etc

The function `pgr_dijkstraNear` is on the develop version (3.2.0-dev) of pgRouting. To use it you would need to compile and build the branch `develop` of the repository.

Documentation: Have not got time to publish latest documentation of that develop branch, as soon as its available I will post it here in another comment

On the meantime you can read the non processed documentation file here: https://github.com/pgRouting/pgrouting/blob/develop/doc/dijkstra/pgr_dijkstraNear.rst

The examples mentioned in that file are here: https://github.com/pgRouting/pgrouting/blob/develop/docqueries/dijkstra/doc-pgr_dijkstraNear.result

It is a steiner tree you are looking for, explained here: https://blog.routeware.dk/2018/05/29/steiner-tree/ I don't think it is part of pgrouting.

If you're looking for an Open Source solution maybe you can make use of the "Minimum Spanning Tree" function(s) of pgRouting. There are a few options: https://docs.pgrouting.org/dev/en/spanningTree-family.html

• thanks. It is close to what I want. However, for me I also need to include source and targets. The tree should be then applied among the targets with the closest connection to any of the sources. Something like a forest instead of a single tree – JoeBe Nov 26 '20 at 23:24
• I'm not sure I understand exactly the use case, but feel free to also share it on our pgRouting chat channel, because most developers are active there and maybe someone can help: gitter.im/pgRouting/pgrouting – dkastl Nov 27 '20 at 0:11