Neo4j shortest path with node properties

Question

I am trying to perform shortest path on neo4j. However, my edges do have costs, as well as the nodes. I want the shortest path in terms of minimizing (node costs + edge costs).

Is there a way of doing that?

Alternatively, I would have to add node costs to edge costs. Would there then be a way to do this dynamically? Like defining edge costs as edge costs = edge costs + successor node costs.

Answer 1

You can find weighted shortest paths using one of the GDS path finding algorithms. The algorithms expect the costs to be a relationship property, so to include the properties from the nodes in the path, you would have to add them the relationship properties as part of the graph projection (it won't modify the relationships in the database, only in the projected graph).

Here is a trivial graph to illustrate, where the cost on the nodes are properties e, and the costs on the relationships are properties d:

CREATE (a:A)-[:R {d: 1}]->({e: 2})-[:R {d: 1.5}]->({e: 1.3})-[:R {d: 1}]->(b:B {e: 2}),
       (a)-[:R {d: 1}]->({e: 11})-[:R {d: 1}]->(b)

First project a graph where the property cost of the relationships is the sum of the d of the original relationship and the property e of their target nodes:

MATCH (source)-[rel]->(target)
RETURN gds.graph.project(
  "example", 
  source, 
  target, 
  { relationshipProperties: { cost: rel.d + target.e } }
) AS g

As an example, here is how get the shortest distance between nodes with label A and nodes with label B using Dijkstra:

MATCH (source:A), (target:B)
CALL gds.shortestPath.dijkstra.stream(
  "example", 
  {
    sourceNode: source, 
    targetNode: target, 
    relationshipWeightProperty: "cost"
  }
)
YIELD path
RETURN path