Neo4j: Shortest Path with Cost Function depending

问题:

Say I have a graph with nodes representing cities and and relations representing possible connections between cities. A connection has a departure and an arrival time. I want to find the shortest path between cities A and B and the cost function is the total travel time. The travel time is the sum of waiting times between connections and connection times.

I'm using the Java API and I have tried using the Dijkstra algorithm using GraphAlgoFactory.dijkstra(expander, costEvaluator). My main problem seems to be, that the CostEvaluator interface only receives the current relation and not the complete path. This way I can compute the connection duration but not the waiting time.

Is there something I can do to adapt the existing algorithm or do I have to reimplement Dijkstra?

回答1:

The total cost of a path will be the sum of the getCost() returned values of every evaluation of the given relationship, so just define how the cost should be evaluated on the relationship level, what the total cost will be is evaluated by the algorithm itself.

On the other hand, you can do it with Cypher, assuming the waiting time is the difference between departure_time and arrival_time :

MATCH p=(a:City {name:"NY"})-[r:CONNECTS*..10]->(b:City {name:"LA"})
WITH p, reduce(
  cost=0, x IN rels(p) | cost + (x.departure_time - x.arrival_time) 
) as cost
RETURN p, cost
ORDER BY cost ASC
LIMIT 1