1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Neo4j shortest path optimization</title>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Neo4j shortest path optimization</title>
<link rel="stylesheet" href="/assets/css/main.css">
<link rel="stylesheet" href="/assets/css/skeleton.css">
</head>
</head>
<body>
<div id="nav-container" class="container">
<ul id="navlist" class="left">
<li >
<a href="/" class="link-decor-none">hme</a>
</li>
<li class="active">
<a href="/log/" class="link-decor-none">log</a>
</li>
<li >
<a href="/projects/" class="link-decor-none">poc</a>
</li>
<li >
<a href="/about/" class="link-decor-none">abt</a>
</li>
<li>
<a href="/cgi-bin/find.cgi" class="link-decor-none">sws</a>
</li>
<li>
<a href="/feed.xml" class="link-decor-none">rss</a>
</li>
</ul>
</div>
<main>
<div class="container">
<div class="container-2">
<h2 class="center" id="title">NEO4J SHORTEST PATH OPTIMIZATION</h2>
<h6 class="center">06 MARCH 2018</h5>
<br>
<div class="twocol justify"><p>Replaced Dijkstra’s for vessel route tracking in Neo4J.</p>
<p>Tracking 13,000 marine vessel route points. Needed shortest paths between ports
for arrival prediction. Neo4j’s Dijkstra’s algorithm slows after 4,000 route
points.</p>
<p>Implemented A* search using haversine function as heuristic:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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;
}
</code></pre></div></div>
<p>Core search loop updates costs when better path found:</p>
<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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);
}
}
</code></pre></div></div>
<p>Outcome: 300x speedup. Scaled to 13,000 route points. Upstreamed changes. <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" class="external" target="_blank" rel="noopener noreferrer">Neo4J v3.4.0</a>.
<a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/blob/bd9732d9a690319552e134708692acb5a0d6b37c/algo/src/main/java/org/neo4j/graphalgo/impl/ShortestPathAStar.java">Full source</a></p>
</div>
<p class="post-author right">by W. D. Sadeep Madurange</p>
</div>
</div>
</main>
<div class="footer">
<div class="container">
<div class="twelve columns right container-2">
<p id="footer-text">© ASCIIMX - 2025</p>
</div>
</div>
</div>
</body>
</html>
|
