How to find the shortest path with the minimum number of transitions in Neo4j?

Question

Im simulating a graph where the nodes are places and the edges indicate that you can move from one place to another.

This should be all the routes that you can take from one place to another, and you can go from one place to another in different ways, so I need a query that returns me the shortest path with minimal changes to the route.

For example, I want to go from A to D, I have two possible ways:

(place {name: "A"})-[:FOLLOWS{route:""R1}]->(place{name: "B" })-[:FOLLOWS{route:""R4}]->(place{name:"C"})-[:FOLLOWS{route:""R2}]->(place{name:"D"}) (place {name: "A"})-[:FOLLOWS{route:""R1}]->(place{name: "B" })-[:FOLLOWS{route:""R1}]->(place{name:"F"})-[:FOLLOWS{route:""R2}]->(place{name:"D"}) 

In the previous two ways, both sizes are the same size, but I would like to get a second that has minimal route changes.

Thanks.

Answer 1

I think this will satisfy your needs. He finds all the shortest paths. Then it processes each of them to count the number of route changes. He then orders the result set by least changing the route and limits the result set to the first occurrence.

 // find all of the shortest paths that match the beginning and ending nodes match p=allShortestPaths((a:Place {name: 'A'})-[:FOLLOWS*]->(d:Place {name: 'D'})) // carry forward the path, the relationships in the path and a range that represents the second to last relationships in the path with p,relationships(p) as rel, range(1,length(p)-1) as index // use reduce to process the route attribute on the relationship to accumulate the changes with p, rel, index, reduce (num_chg = 0, i in index | num_chg + case when (rel[i]).route = (rel[i-1]).route then 0 else 1 end ) as changes // return the path and the number of route changes return p, changes // only return the path with the fewest route change order by changes limit 1 

Answer 2

@DevBennett responds to the shortest path with the least number of route changes.

To get the shortest path with the minimum number of different routes, which is literally asked a question (but which, perhaps, was not what the person wanted), you can use this query:

 MATCH p=ALLSHORTESTPATHS((a:Place {name: "A"})-[:FOLLOWS*]->(d:Place{name:"D"})) UNWIND RELATIONSHIPS(p) AS rel WITH p, COUNT(DISTINCT rel.route) AS nRoutes RETURN p, nRoutes ORDER BY nRoutes LIMIT 1; 

Answer 3

Something like that:

 MATCH (a:place {name: "A"}) WITH a MATCH (d:place {name: "D"}) WITH a,d MATCH p = allShortestPaths ( (a)-[:FOLLOWS*..100]->(d) ) WITH nodes(p) as places, relationships(p) as paths UNWIND paths as path WITH places, paths, collect(distinct path.route) as segments RETURN places, paths, segments, size(segments) as cost ORDER BY cost ASC LIMIT 1 

Answer 4

Come on, you could not be satisfied with only 3 answers :)

 MATCH (a:Place {name:"A"}), (d:Place {name:"D"}) MATCH p=allShortestPaths((a)-[*]->(d)) RETURN p, size(filter(x in range(0, size(rels(p))) WHERE (rels(p)[x]).route <> (rels(p)[x-1]).route)) + length(p) as score ORDER BY score ASC 

Answer 5

Answers using "AllShortestPaths" are incorrect.

What if the graph looks like the image below?

Graph Example Well, the result of queries using the AllShortestPaths function will be "AED", not "ABCD" ...