SHORTESTPATH and ALLSHORTESTPATH

[bini_sajit]

CREATE (AT:Airport { city:'Atlanta' }),(CH:Airport { city:'Chicago' }),(LA:Airport { city:'Los Angeles' }),(DA:Airport { city:'Dallas' }),(AU:Airport { city:'Austin' })

CREATE (AT)-[:ROUTE { time:22 }]->(AU), (AU)-[:ROUTE { time:35 }]->(LA), (AT)-[:ROUTE { time:40 }]->(DA), (DA)-[:ROUTE { time:34 }]->(LA), (CH)-[:ROUTE { time:13 }]->(AT), (LA)-[:ROUTE { time:63 }]->(CH)

Created the above nodes and relationship
When I try using SHORTESTPATH between the node CH and LA, I am getting the time as 87 instead of 70. Why is this happening?

What is the difference between ShortestPath and AllShortestPaths and how will be the output in the same context?

[andrew_bowman]

Which calls are you using here? if you're just using shortestPath() or allShortestPaths(), these don't account for weighted properties, they're purely in terms of the number of hops between the nodes. If you need property weights to be considered, you need a different approach, such as using the graph algo library.

[ameyasoft]

Hi

Try this:

MATCH p=(c:Airport)-[:ROUTE*]->(l:Airport)
WHERE c.city = "Chicago" and l.city = "Los Angeles"
RETURN p as shortestPath, reduce(time=0, r in relationships(p) | time+r.time) AS totalTime ORDER BY totalTime ASC LIMIT 1;

-Kamal

[jasperblues]

In my traffic routing blog over on https://liberation-data.com/blog.html, I show you how to simulate a weighted graph, by finding candidate paths, and reducing to the most expedient route.

However it is a great suggestion by Andrew Bowman to look at the Graph Algorithms library, and use a weighted graph algorithm from there.

[bini_sajit]

I tried this too , still it gives me the larger time. Is this a bug in Neo4j as I tried with another set of values i.e added two more paths of length 2 and then it worked

Thanks for your prompt response

[fraboi87]

ameyasoft:

MATCH p=(c:Airport)-[:ROUTE*]->(l:Airport)
WHERE c.city = "Chicago" and l.city = "Los Angeles"
RETURN p as shortestPath, reduce(time=0, r in relationships(p) | time+r.time) AS totalTime ORDER BY totalTime ASC LIMIT 1;

Does this query check for coincidence constraint, i.e., check that the next ROUTE has a departing time bigger than the arrival of the previous?

[jasperblues]

@bini.sajit Please clarify:

What would you like to achieve?

If you want to calculate the most expedient route, it may not be the shortest path in terms of hops, as it depends on the summation of the time properties on the ROUTE relationship between the a-end and the b-end. As Andrew Bowman said, this is called a weighted graph. You could:

• Use plain CYPHER to find a set of candidate paths, then reduce to the most expedient route. (I linked to a blog post on this above. Here's another from Adam Cowley here: https://neo4j.com/blog/journey-planning-why-i-love-cypher/). This can be efficient for quite large datasets.
• If you want the most performance optimal solution, you can install from the graph algorithms plugin package, and use an algorithm that finds paths against a weighted graph.

[bini_sajit]

Request u to share the code using graph algorithm to achieve choosing path with cost property. Also mention the prerequisites for using the algorithm

[andrew_bowman]

The documentation for the shortest path algo in the Neo4j Graph Algorithms documentation includes description, when to use, and examples.

[ameyasoft]

Hi Andrew,

Thanks for suggesting to use graph algorithms. I played with 'Minimum Weight Spanning Tree algorithm', 'K-Spanning tree', and 'The Dijkstra Shortest Path algorithm' They all produced the same result as shown in my earlier reply. Finally, 'Delta stepping algorithm' worked well for this scenario.

Here is the Cypher query:

MATCH (n:Airport {city:"Chicago"})
CALL algo.shortestPath.deltaStepping.stream(n, 'time', 3.0, {relationshipQuery:'ROUTE',direction:'OUTGOING'})
YIELD nodeId, distance
RETURN algo.getNodeById(nodeId).city AS destination, distance ORDER BY distance asc;

Result:

Hope my findings are correct.

-Kamal

[ameyasoft]

The selection of relationship direction in Delta stepping algorithm helped to solve this problem. In the present scenario there is a non-stop service between Los Angeles and Chicago and this is inbound with respect to Chicago node. I did not see this feature in other algorithms. Delta stepping algorithm also produces the same result as other algorithms if you do not select the direction.

-Kamal

[ameyasoft]

Hi,

You should have Neo4j 3.5.0 and APOC library 3.5.0.1.

-Kamal

[jasperblues]

I believe I saw a report that earlier versions of algo.shortestPath.allShortestPaths were not able to disregard relationship direction, however it can now. Will test this later.

Update: https://liberation-data.com/saxeburg-series/2018/12/05/rock-n-roll-traffic-routing.html
^--- Here's a post about using Djikstra's shortest path algorithm for weighted graphs.