のNeo4j - リレーションシップ・プロパティに基づいて、2つのノード間の最短経路を見つける

Question

私はこの例で与えられ、関係の総和に基づいて、2つのノード間の最短距離を得るために何らかの方法があるかどう把握しようとしている： 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

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には最短のPath（）関数があり、これは述語と組み合わせて試行錯誤して、おそらくあなたが望むことをするでしょう。

しかし、時間を節約するために、neo4j APOC Proceduresを使用する方が簡単です。重み付けされたdijkstra最短経路アルゴリズムが含まれています。このアルゴリズムは、あなたが望むものに最適です。

については

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

のようなものを私はまだそれを使用していないが、私は（あなたの関係の名前と重量のために使用されるプロパティを使用して、startNodeとエンドノード上でマッチング後）の構文を考えている

wikiのドキュメントはそれを完全には説明していませんが、<または>が関係ラベルの適切な末尾に追加されていると思われますので、 'distance>'はおそらくより正確なパラメータです方向性を尊重したいサイファーで