Neo4j : 경로의 두 연속 관계에 따라 비용 함수가있는 최단 경로

노드 사이에 가능한 연결을 나타내는 노드와 관계를 나타내는 노드가 있다고 가정 해보십시오. 연결에는 출발과 도착 시간이 있습니다. 도시 A과 B 사이의 최단 경로를 찾고 비용 함수는 총 소요 시간입니다. 이동 시간은 연결 사이의 대기 시간과 연결 시간의 합입니다.Neo4j : 경로의 두 연속 관계에 따라 비용 함수가있는 최단 경로

Java API를 사용하고 있으며 GraphAlgoFactory.dijkstra(expander, costEvaluator)을 사용하여 Dijkstra 알고리즘을 사용해 보았습니다. 내 주요 문제는 것 같습니다, CostEvaluator 인터페이스는 현재의 관계와 전체 경로를받지 못합니다. 이 방법으로 연결 기간을 계산할 수 있지만 대기 시간은 계산할 수 없습니다.

기존 알고리즘을 적용하기 위해 할 수있는 일이 있습니까, 아니면 Dijkstra를 다시 구현해야합니까?

출처

2016-09-14 Kirill Rakhman

당신이 waiting_time'이 DEPARTURE_TIME'의 결과는'확인 할 수 - arrival_time' ? –

나는 아래에서 설명했다. –

경로의 총 비용은 제공된 관계의 모든 평가에 대한 getCost() 반환 값의 합계가 될 것이므로 관계 수준에서 비용을 평가하는 방법, 총 비용이 어떻게 계산되는지를 정의하십시오. 알고리즘 그 자체. 당신은 대기 시간을 가정, 사이퍼와 함께 할 수있는 반면에

는 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

출처

2016-09-14 15:18:45

Cypher 버전이 최적화되어 있습니까? –

아니요, dijkstra 알고리즘이 더 우수한 성능을 발휘할 수 있습니다. 지금은 테스트 할 기회가 없습니다. –

데이터가 많아 성능이 중요합니다. 또한 오해가 있다고 생각합니다. 관계'r'의 비용은'r.arrival - r.departure + r.departure - r_previous.arrival'이어야하며'r.departure - r_previous.arrival'로 단순화 될 수 있습니다. –

Neo4j : 경로의 두 연속 관계에 따라 비용 함수가있는 최단 경로

답변

관련 문제