Finding a route through N nodes with a length of no more than T

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Hello everyone, help with the implementation of the following task is needed.
There are Point nodes containing coordinates (lat, lng). There is a bidirectional relationship (from point A to B and from point B to A) DIRECTIONS between each node, which contains the distance property (distance of pedestrian route in meters). Thus, we have a complete graph - Complete graph - Wikipedia. We know point A from which the tourist will start the route. It is necessary to find the first route that will pass through N nodes and its length should not exceed T meters.
Please advise which strategy/algorithm to use for route search?
Thanks for your time

2

Hi @mfiyalka,

When you say the first route that will pass through N nodes and not exceed T meters, are you asking for the shortest route that will pass through at least N nodes?

A tourist starts a journey at A. We can find all their journeys that will be less than T meters and include exactly N nodes. Do you want all of those journeys as part of the result, or just one of them?

Best wishes,
Nathan

3

I'm sorry, I phrased my question a bit incorrectly. What I meant was that the length of the route should also be limited, meaning that the tourist should visit N establishments, where the length of the route should be between T1 and T2 meters.

I just want one route.

4

Here's a query I might use to get a path with 5 establishments.

MATCH p = (:POI {id:$startId})-[r:HAS_ROUTE WHERE r.distance < $T2]-{4}()
WHERE $T1 < reduce(total = 0.0, d in r | total +  d.distance) < $T2
AND size(apoc.coll.toSet(nodes(p))) = 5
RETURN [y in nodes(p) | y.id] AS ids, 
reduce(total = 0.0, d in r | total +  d.distance) AS totalDistance 
LIMIT 1

It is checking each potential relationship to make sure that it's distance is less than T2 before adding it to the path. After assembling a path, it checks to make sure that the total distance is between T1 and T2. It also checks to make sure that there are five nodes in the path to ensure that no establishments were repeated.

Does that perform well enough for what you need?

1 Like
5

Thank you for your help