如何在Neo4j中找到跳数最少的最短路径？ [英] How to find the shortest path with the minimum number of hops in Neo4j?

问题描述

我建模一个图形，其中节点是地方和边缘表示你可以从一个地方去另一个地方。

这是让所有路线都可以从一个地方转到另一个地方，
，并且您可以通过不同的路线从一个地方转到另一个地方，所以我例如，我想从A到D，我有两条可能的路径：

（place {name：A}） - [：FOLLOWS {route：R1}] - >（place {} {$ p
$ b

 名称：B}） -  [：FOLLOWS {route：R4}]  - >（place {name：C}） -  [：FOLLOWS {route：R2}]  - >（place {名称：D}）
 
（place {name：A}） -  [：FOLLOWS {route：R1}]  - >（place {name：B}） -  [：遵循{路线：  R1}]  -  GT;（地方{名称： F}） -  [：遵循{路线：  R2}]  -  GT;（地方{名： d}） 
  

在之前的两个路径中，两个都是相同的大小，但我想获得第二个，这是谁有最小的路线变化的人。

谢谢。

解决方案

我认为这会满足你的需求。它找到所有最短的路径。然后它处理每一个来计算路线变化的数量。然后它通过最少的路线变化来命令结果集，并将结果集限制在第一次出现的位置。

  //找到所有匹配开始和结束节点的最短路径
 match p = allShortestPaths（（a：Place {name：'A'}） -  [：FOLLOWS *]  - >（d：Place {name：'D' }））
 
 //传递路径，路径中的关系以及表示路径中第二个到最后一个关系的范围
 with p，关系（p）为rel，范围（1，length（p）-1）作为索引
 
 //使用reduce来处理关系中的路由属性以累积变化
 with p，rel，index，reduce（ num_chg = 0，i在index | num_chg + 
的情况下（rel [i]）。route =（rel [i-1]）。route然后0 else 1 end）作为变化
 
 //返回路径和路线变化的数量
返回p，变化
 
 //仅返回路径变化最少的路径
变化的顺序
限制1 
  

Im modeling a graph where nodes are places and edges indicate that you can go from one place to another.

This is to have all routes that you can take from a place to another, and you can go from a place to another by different routes, so I want a query that returns me the shortest path with the minimum route changes.

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

(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 path, both are the same size, but I would like to get the second one, which is the one who has the minimum route changes.

Thank you.

解决方案

I think this will meet your needs. It finds all of the shortest paths. Then it processes each one to count the number of route changes. It then orders the result set by the fewest route changes 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

这篇关于如何在Neo4j中找到跳数最少的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！