的Neo4j - 尋找基於關係屬性兩個節點之間的最短路徑

Question

我試圖找出是否有要想辦法讓基於關係和兩個節點之間的最短距離，因爲這個例子： neo4j image example

碼爲上圖：

CREATE (some_point_1:Point {title:'Some Point 1'}) 
CREATE (some_point_2:Point {title:'Some Point 2'}) 
CREATE (some_point_3:Point {title:'Some Point 3'}) 
CREATE (some_point_4:Point {title:'Some Point 4'}) 
CREATE (some_point_5:Point {title:'Some Point 5'}) 
CREATE (some_point_6:Point {title:'Some Point 6'}) 

CREATE (some_point_1)-[:distance {value:100}]->(some_point_2) 
CREATE (some_point_2)-[:distance {value:150}]->(some_point_4) 
CREATE (some_point_1)-[:distance {value:200}]->(some_point_3) 
CREATE (some_point_3)-[:distance {value:300}]->(some_point_4) 
CREATE (some_point_2)-[:distance {value:500}]->(some_point_5) 
CREATE (some_point_4)-[:distance {value:300}]->(some_point_5) 
CREATE (some_point_5)-[:distance {value:300}]->(some_point_6) 
CREATE (some_point_6)-[:distance {value:300}]->(some_point_1) 

在本例中的最短路徑應該是： some_point_1> some_point_2> some_point_4> some_point_5（100 + 150 + 300 = 550）

Cypher有這種可能嗎？

Answer 1

在Cypher支架的shortestPath功能不考慮積累的關係性質的，所以這一點：

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'}) 
MATCH p=shortestPath((start)-[:distance*]->(end)) 
RETURN p 

會發現基於路徑的數量關係從start到end的最短路徑。

你可以對距離的總和減少：

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'}) 
MATCH p=(start)-[:distance*]->(end) 
WITH p,reduce(s = 0, r IN rels(p) | s + r.value) AS dist 
RETURN p, dist ORDER BY dist DESC 

但這裏的問題是，你需要計算從start到end所有路徑的總距離。爲了更高效，您希望使用像Dijkstra's algorithm或A *這樣的圖搜索算法，它們都在Neo4j's Java API中實現。

在Neo4j 3.0中，這些算法通過APOC procedure library在Cypher中公開。一旦安裝APOC，您可以致電Cypher的程序：

MATCH (start:Point {title: 'Some Point 1'}), (end:Point {title: 'Some Point 5'}) 
CALL apoc.algo.dijkstra(start, end, 'distance', 'value') YIELD path, weight 
RETURN path, weight 

Answer 2

Cypher有一個shortestPath（）函數，結合謂詞和一些試驗和錯誤可能會做你想做的。

但爲了節省時間，它更容易使用neo4j APOC Procedures，其中包括加權dijkstra最短路徑算法，應該是一個完美適合你想要的。

我還沒有使用它，但我認爲語法（上的StartNode和終端節點匹配，使用你們的關係的名稱，用於重屬性後）是一樣的東西

CALL apoc.algo.dijkstra(startNode, endNode, 'distance', 'value') 
YIELD path, weight 

至於考慮到方向，維基文檔沒有直接說明，但它看起來像<或>被添加到關係標籤的適當的末尾，我認爲，所以'距離>'可能是更正確的參數，如果你要它尊重方向。