Shortest path using query

[Johan Kumps]

Hi,

I'm currently calculating the shortest paths between 2 nodes via the SEM_SIM relationship using the following query:

@Query("MATCH (s:StartVertex {uuid:{0}}) , "

+ "(g:GoalVertex {uuid:{1}}) , "

+ "path = shortestpath((s)-[:SEM_SIM*]-(g)) "

+ "RETURN path ORDER BY LENGTH(path) DESC LIMIT 1")

All this is working fine but I would like to be able to take a relationship attribute like cost into account. How can I use this attribute in the above query?

Thanks in advance for the information

Kind regards,

Johan,

[Michael Hunger]

Just add a WHERE clause (at least in Neo4j 3.x)

WHERE ALL( rel in rels(path) WHERE rel.cost > 10)

> --
> You received this message because you are subscribed to the Google Groups "Neo4j" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Johan Kumps]

What if I would like to get all shortest paths with the lowest cost without knowing how much this could be. I think by adding the query rel.cost < x will not work in this case?

Op dinsdag 17 mei 2016 22:23:37 UTC+2 schreef Michael Hunger:

[Craig Taverner]

If you want the shortest path to interpret the length of the path based on a cost function (for example shortest route on the map where the length of the roads is the cost), then the 'shortestPath()' function is not the right one. It can only consider all relationships as having the same weight and that is the nature of the optimization of that algorithm. You need a different algorithm like dijkstra or A-star. Cypher does not have integration to the graph-algo component that provides those algorithms, so you have three choices:

* Write an exhaustive cypher query that finds all paths, sums the cost and sorts and orders. This is fine on small graphs, but will be extremely slow on even medium sides graphs.

* Use the graph-algo module through the Java API (unmanaged extensions in neo4j 2.3 and earlier)

* Use the new procedures from Cypher in Neo4j 3.0 and later (these are already wrapped for you at https://github.com/neo4j-contrib/neo4j-apoc-procedures#graph-algorithms-work-in-progress)

This last option is probably the easiest option, but I've not tried them myself. Michael might know better how well they work.

[Johan Kumps]

Thanks for your answers.

As said I'm using Neo4J 2.2.5 together with Spring-data. Could you please provide me an example of this Dijkstra approach. If needed I can upgrade the Neo4J library. I do want however to be able to use the spring data and Cypher approach.

Thanks in advance.

Johan,

Op dinsdag 17 mei 2016 22:57:31 UTC+2 schreef Craig Taverner: