---
title: 'Neo4J path traversal: A* optimization'
date: 2018-03-06
layout: post
---
Work. Vessel tracking with Neo4J hit a limit. Need to analyze 13,000 route
points; Dijkstra's shortest path search slows after 4,000.
Replaced Dijkstra's algorithm with A* search using haversine function as
heuristic:
```
private double computeHeuristic(
final double lat1, final double lon1,
final double lat2, final double lon2) {
final int earthRadius = 6371;
final double kmToNM = 0.539957;
final double latDistance = Math.toRadians(lat2 - lat1);
final double lonDistance = Math.toRadians(lon2 - lon1);
final double a = Math.sin(latDistance / 2)
* Math.sin(latDistance / 2)
+ Math.cos(Math.toRadians(lat1))
* Math.cos(Math.toRadians(lat2))
* Math.sin(lonDistance / 2)
* Math.sin(lonDistance / 2);
final double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return earthRadius * c * kmToNM;
}
```
Core search loop updates costs when better path found:
```
private void updateCosts(
final int source, final int target,
final double newCost, final double heuristic) {
final double oldCost = gCosts.getOrDefault(target, Double.MAX_VALUE);
if (newCost < oldCost) {
gCosts.put(target, newCost);
fCosts.put(target, newCost + heuristic);
path.put(target, source);
}
}
```
300x speedup. Scaled to 13,000 route points.
Upstreamed changes: Neo4J v3.4.0 |
Full source.