How to find shortest path in neo4j with property filters but without GDS?

Question

I want to find a shortest path in neo4j between a start and end node. The graph is weighted with properties "costs" and "transit_time".

I wanna find the shortest path in terms of transit_time. However, for this I only want each relationship to have costs below 1000. Requirement is, I cannot use GDS. In fact, I cannot use anything that creates a sub-graph (so apoc subgraph is also not an option). I tried this with APOC

MATCH (start:Node {id: 'startId'}), (end:Node {id: 'endId'})
CALL apoc.algo.dijkstra(start, end, 'REL1|REL2', 'transit_time') YIELD path, weight
WHERE all(r in relationships(path) WHERE r.costs < 1000)
RETURN path, weight

However, if the shortest path found does not match WHERE criteria, I get nothing. How can I tell Dijkstra function to only consider specific relationships that match the condition?

I found this discussion on GitHub: https://github.com/neo4j/apoc/issues/136

However, seems like there was no solution for that within APOC (as of Sep 2022). So I continue looking for a workaround.

Kind regards and thanks for your help!

Finbar Good · Accepted Answer · 2024-08-19 10:34:34Z

2

A reason why you might be getting no answers is that the shortest path by weight transit_time returns a path with at least one relationship with cost >= 1000.

If you were able to use GDS you could eliminate the relationships with cost >= 1000 during projection and then use gds.shortestPath.dijkstra.

But as you say this isn't an option, an alternative is to use the last parameter of apoc.algo.dijkstra to return the N shortest paths, filter out any paths with cost >= 1000, and pick the shortest using ORDER BY weight LIMIT 1:

MATCH (start:Node {id: 'startId'}), (end:Node {id: 'endId'})
CALL apoc.algo.dijkstra(start, end, 'REL1|REL2', 'transit_time', NaN, 10) 
YIELD path, weight
WHERE all(r IN relationships(path) WHERE r.costs < 1000)
RETURN path, weight ORDER BY weight LIMIT 1

Here I set N = 10. The catch is that picking a value for N is arbitrary, all N shortest paths may still all fail your test, and possibly the algorithm does more work than necessary.

A brute force approach will definitely return a result (if there is a path) but could be prohibitively expensive:

MATCH path = (start:Node {id: 'startId'})-[rel:REL1|REL2 WHERE rel.costs < 1000]-+
             (end:Node {id: 'endId'})
WITH path, reduce(acc = 0, r IN relationships(path) | acc + r.transit_time) AS weight
RETURN path, weight ORDER BY weight LIMIT 1

answered Aug 19, 2024 at 10:34

Finbar Good

1,6012 gold badges10 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

thomaswiiswitch Over a year ago

You're right, this might be the reason. However, for my use case it is not acceptable to create a subgraph first. As I understood, this is a requirement for GDS.

cybersam Over a year ago

The GDS does not "require" you to change your stored data. It is just that sometimes the stored data is not already structured in the right way to make use of some GDS feature. I suspect that in your use case no stored-data changes would be needed to use the GDS.

thomaswiiswitch Over a year ago

Thanks for response! But as I understood, it's required to create some kind of in-memory-subgraph before applying GDS-Shortest-Path-Algorithms. Or is there any other way?

Finbar Good Over a year ago

My suggestions don't require GDS, in case you missed that. You are right that you need to create an in-memory graph with projection to use the GDS shortest algorithms, but as @cybersam says, that doesn't modify any data.

Collectives™ on Stack Overflow

How to find shortest path in neo4j with property filters but without GDS?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related