Orienteering with Neo4j - solving the 1000-control race with the Dijkstra-APOC - part 2/2

In part 1 of this blogpost, I explained how you can use the Awesome Neo4j APOCs to calculate a weighted shortest path on a graph with a more optimized and more efficient algorithm, based on Dijkstra's work. In this second and last blogpost on this topic, I would love to explain a bit why I think this is pretty much a very big deal. APOCs give you access, from Cypher, to a whole slew of graph algorithms, many of them very useful for all kinds of different graph operations.

Orienteering - a bit more complicated in the real world

One reason why I wanted to write this second post, is of course because my lovely sport - Orienteering - is of course a bit more complicated in the real world than what you have seen in that little park run that I talked about in the previous two posts. To give you a feel for it:

• Here's an excerpt of my run in the World Masters Orienteering Champs a few weeks back in Estonia. More details over here - but I can tell you that for each and every one of these legs there's at least half a dozen different route options - and of course my course had 20+ control points too. So a bit more of a bigger graph anyway!
• And here's another example: actually being run today (August 25th) is the actual elite's World Orienteering Champs on the long distance. Just. Look. At. This. Map.

Orienteering with Neo4j - moving from Cypher to the Dijkstra-APOC - part 1/2

So last July, my dear colleagues at Neo4j decided that they would tweet about a blogpost that I wrote 3 years ago.

#tbt: Finding the Shortest Path through the Park (with Graphs!)https://t.co/CLlK5Izuxk
via @rvanbruggen pic.twitter.com/SgbLYBUrRC

— Neo4j (@neo4j) July 28, 2016

The post was first published on my own blog over here, and then re-blogged over at the neo4j.com/blog. I also wrote a graphgist about it at the time, which I have revisited on the graphgist portal just now.

Some context

This entire thing started that summer with a blogpost by my friend and (at the time) colleague, Ian Robinson, about using a clever cypher query to calculate the weighted shortest path over a (small) graph. I decided to use that mechanism and apply it to my lovely hobby/sport: Orienteering. Pathfinding through forests, parks, cities - it's what we do in that sport, all the time. And efficient pathfinding in this environment, requires you to read the map, understand what the fastest route is, and run that as fast as you can. Effectively, when you want to "understand the fastest route", you will be weighing different alternative route choices against one another, and - as quickly as you can - choose that one for your run. It is, in effect, a total graph problem, a total "weighted shortest path problem" on a detailed map of your surroundings. So I used Ian's approach, and applied it to a small graph of an orienteering excercise in an Antwerp park.