From 9ac8970b08550a83e9ba686d0e9357654373a047 Mon Sep 17 00:00:00 2001 From: Sadeep Madurange Date: Fri, 19 Dec 2025 21:32:28 +0800 Subject: Neo4J. --- _blog/neo4j-a-star-search.md | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) (limited to '_blog/neo4j-a-star-search.md') diff --git a/_blog/neo4j-a-star-search.md b/_blog/neo4j-a-star-search.md index 117931b..e52dad9 100644 --- a/_blog/neo4j-a-star-search.md +++ b/_blog/neo4j-a-star-search.md @@ -7,24 +7,23 @@ layout: post Back in 2018, we used Neo4J graph database to track the movement of marine vessels. We were interested in the shortest path a ship -could take through a network of about 13,000 route points. Algorithms based on -graph theory, such as A* search, provide optimal solutions to such problems. -In other words, the set of route points lends itself well to a model based on -graphs. +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling. A graph is a finite set of vertices, and a subset of vertex pairs (edges). Edges can have weights. In the case of vessel tracking, the route points form -the vertices of a graph; the routes between them, the edges; and the distances -between them are the weights. For different reasons, people are interested in -minimizing (or maximizing) the weight of a path through a set of vertices. For -instance, we may want to find the shortest path between two ports. - -Given such a graph, an algorithm like Dijkstra's search could compute the -shortest path between two vertices. In fact, this was the algorithm Neo4J -shipped with at the time. One drawback of Dijkstra's algorithm is that it -computes all the shortest paths from the source to all other vertices before -terminating at the destination vertex. The exhaustive nature of this search -limited our search to about 4,000 route points. +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel's arrival time. + +Given a graph, an algorithm like Dijkstra's search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra's algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points. The following enhancement to Dijkstra's search, also known as the A* search, employs a heuristic to steer the search in the direction of the destination @@ -314,5 +313,5 @@ significantly speed up the search. In our case, we achieved a 300x speedup, enabling us to expand our search from 4,000 to 13,000 route points. The v3.4.0 of the -Neo4J graph algorithms shipped with the A* search algorithm. +Neo4J graph algorithms shipped with our A* search algorithm. -- cgit v1.2.3