# Minimum spanning tree (MST) over a set of POINT geometries

I have 3 columns in my table: centerPoint (point), uuid (string), and "areaID".

Each areaID can have multiple uuid's, and each uuid has a corresponding centerPoint. I want to calculate the shortest path through all the centerPoints of a particular "areaID", and I want the relevant uuid's to be listed along the path.

I am following this resource in its implementation, as recommended by @geozealot.

Here is my modified code:

``````WITH RECURSIVE
tree AS (
SELECT
g."centerPoint"::GEOMETRY AS vtcs,
NULL::GEOMETRY AS segment,
ARRAY[g.uuid] AS uuids
FROM
potential_missed_areas AS g
WHERE
g."areaID"  =  '007af142-75a3-4678-975a-29f78b92af05'
and g.status = 'approved'
UNION ALL
SELECT
ST_Union(t.vtcs, v."centerPoint"),
ST_ShortestLine(t.vtcs, v."centerPoint"),
t.uuids || v. uuid
FROM
tree AS t
CROSS JOIN LATERAL (
SELECT
g. uuid  , g."centerPoint"
FROM
potential_missed_areas AS g
WHERE
NOT g. uuid   = ANY(t.uuids)
ORDER BY
t.vtcs  <->   g."centerPoint"
LIMIT
1
) AS v
)
SELECT
segment
FROM
tree
WHERE
segment IS NOT NULL
;
``````

The problem is that this generates a result set with 5,184 rows, whereas this particular areaID has only 6 uuid's.

Add the `"areaId"` to the filter criteria in the recursive term, or it will consider rows across all `"areaId"`s to find candidates:

``````...
CROSS JOIN LATERAL (
SELECT
g.uuid,
g."centerPoint"
FROM
potential_missed_areas AS g
WHERE
g."areaId" = <area_id>
AND
NOT g.uuid = ANY(t.uuids)
ORDER BY
t.vtcs <-> g."centerPoint"
LIMIT
1
) AS v
...
``````

You also need to pick a single row (`uuid`) in the driver term, i.e.

``````SELECT
g."centerPoint"::GEOMETRY AS vtcs,
NULL::GEOMETRY AS segment,
ARRAY[g.uuid] AS uuids
FROM
potential_missed_areas AS g
WHERE
g.uuid = <uuid>
...
``````

This query can be enhanced to be more generic, generating MSTs over all partitions you want. But check if MSTs are what you are looking for.

But note that a MST is not the shortest, singular path as in the Traveling Salesman Problem - it is a tree, having branches, with the minimum aggregated connection lengths!

• so the result set can not be used to derive the shortest path? Commented Sep 30, 2023 at 14:32
• if I only take the row from the result set which has the exact number of items that I want, then it would be the result for the TSP problem right? Commented Sep 30, 2023 at 14:38
• RE: too many returned rows: see my update. RE: the TSP: this is much more involved than this point set MST algorithm, and you would need to look into sophisticated graph analytics engines (e.g. pgRouting for PostgreSQL/PostGIS). For 6 points only you could easily brute force the optimal solution (having only `6! = 720` permutations), but double that and your machine will burn. Commented Sep 30, 2023 at 15:05
• thanks, may you live a happy and blessed life! Commented Sep 30, 2023 at 15:09
• My solution creates a Minimum Spanning Tree, which is not the optimized shortest route through all points as in the Travelling Salesman Problem - please research the difference! With regards to what I said: this is meant for the TSP where you could brute force the optimal solution for only 6 points; for 30 points, however, you're looking at `!30 = 2.6 * 10^32` permutations! Commented Oct 9, 2023 at 11:21