Neo4j：経路内の2つの連続関係に依存するコスト関数を持つ最短経路

Question

都市間の可能な接続を表すノードおよび関係を表すノードを持つグラフがあります。接続には出発時刻と到着時刻があります。都市AとBの間の最短経路を探したいと思います。費用関数は合計旅行時間です。移動時間は、接続と接続時間の間の待機時間の合計です。

私はJava APIを使用しており、GraphAlgoFactory.dijkstra(expander, costEvaluator)を使用してDijkstraアルゴリズムを試してみました。私の主な問題は、CostEvaluatorのインタフェースが完全なパスではなく、現在のリレーションのみを受け取るということです。このようにして、接続時間は計算できますが、待ち時間は計算できません。

私は既存のアルゴリズムを適応させるために何かできますか、またはDijkstraを再実装する必要がありますか？

Answer 1

パスの総コストは、与えられた関係のすべての評価の戻り値の合計になります。したがって、コストを関係レベルでどのように評価するか、総コストはアルゴリズムそのもの。

一方、あなたは待機時間がdeparture_timeと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