Neo4j - Die Suche nach dem kürzesten Weg zwischen zwei Knoten, basierend auf Beziehung Eigenschaft

Question

Ich versuche, herauszufinden, ob es irgendwie ist die kürzeste Entfernung zwischen zwei Knoten in einer Beziehung Summe basierten zu erhalten, da dieses Beispiel: neo4j image example

Code für Bild oben:

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) 

In diesem Beispiel sollte der kürzeste Weg sein: some_point_1> some_point_2> some_point_4> some_point_5 (100 + 150 + 300 = 550)

Ist so etwas bei Cypher möglich?

Answer 1

Die shortestPath Funktion in Cypher nicht berücksichtigt in der Beziehung Eigenschaften akkumulieren, so folgt aus:

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

von start zu end den kürzesten Weg basierend auf dem Weg von der Anzahl der Beziehungen finden würde.

Sie könnten auf die Summen der Abstände verringern:

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 

Aber das Problem hier ist, dass Sie die Gesamtstrecke für alle Pfade von start zu end berechnen müssen. Um effizienter zu sein, möchten Sie einen Graphensuchalgorithmus wie Dijkstra's algorithm oder A * verwenden, die beide in Neo4j's Java API implementiert sind.

In Neo4j 3.0 sind diese Algorithmen in Cypher durch die APOC procedure library ausgesetzt. Sobald Sie APOC installiert haben, können Sie die Prozedur von Cypher aus aufrufen:

Answer 2

Cypher hat eine shortestPath() -Funktion, die in Kombination mit Prädikaten und ein wenig Versuch und Irrtum wird wahrscheinlich tun, was Sie wollen.

Aber um Zeit zu sparen, ist es einfacher zu verwenden neo4j APOC Procedures, die einen gewichteten dijkstra kürzesten Pfad-Algorithmus enthält, der eine perfekte Passform für was Sie wollen.

Ich habe es noch nicht benutzt, aber ich denke, die Syntax (nach dem Einschalten startNode und Endknoten übereinstimmt, mit dem Namen Ihrer Beziehung und die Eigenschaft für Gewicht) ist so etwas wie

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

Was Unter Berücksichtigung der Richtung, die Wiki-Dokumentation sagt es nicht direkt, aber es sieht aus wie < oder> wird an das entsprechende Ende der Beziehung Etikett hinzugefügt, denke ich, so 'Abstand>' ist wahrscheinlich der korrektere Parameter, wenn Sie möchte, dass es die Richtung respektiert.