###### By Neo4j Staff | August 19, 2013

**”: the *fastest* route from start to finish. Fast can be short. Fast can also mean that it is better to take a detour: if it is easier to run the longer route, than to walk the shorter route, you are better off choosing the longer route. In essence, every orienteering race is … a graph problem waiting to be solved in the middle of nature.**

__finding the shortest path__

## Orienteering = a green graph problem

In case you don’t know: orienteering races are a bit like an obstacle race. Every participant gets assigned a course, out there in the green forests and fields, and along that course are sequences of beacons that one needs to get to in order. Such a sequence is … a path on a graph – you have to choose how to navigate from obstacle to obstacle, from node to node.

**fastest**route. Finding the fastest route effectively this

__boils down to a “weighted shortest path” calculation__. You calculate the shortest path using

- distance: shorter = better
- runnability: higher = better. Runnability can be affected by the type of terrain (running on a road? through a field? through a forest? through a forest with soil covered with plants? over a hill? through a valley? …)

## Example: a 2 control race in Antwerp, Belgium

The red route is the safe choice – running along the roads – but takes quite a detour. The blue route cuts straight across the field – but then requires me to go straight through the forest for a short distance. | The red route is the shortest – but requires me to run straight through the forest. The blue route just races along the forest road. | The red route just goes straight to the finish line. The blue route cuts through the forest and then follows the road. The green route safely hurries along the roads. |

## Graph database model to navigate

- Control nodes: the race beacons that I have to pass by
- The alternative route choices, decomposed in waypoints.

- From the start to control 1: I have
**0->0.11->0.12->0.13->0.14->0.15**as one route and**0->0.21->0.22->1**as another route - From control 1 to control 2 I have
**1->1.11->1.12->1.13->2**as one route option, and**1->0.15->1.21->2**as another option. - From control 2 to the finish I have 3 options:
**2->2.11->3**,**2->2.21->2.22->3**and**2->1.21->2.31->2.32->3**.

## Graphs algorithms to win the race!

In order to calculate the best route to win the race, I need to calculate the shortest path across the graph – which is standard functionality of neo4j. But because there’s more to it than running the course in straight lines between controls, I need to incorporate**weights**(distance, runnability) to get a realistic estimate of what would be the best route choice. To do so I am using a technique so well demonstrated by Ian Robinson on his blog last June.

- find the shortest path by distance only:

- find the best estimate of the fastest path, as a function of distance/runnability. In a real race this would probably be the route that I would choose – as it would give me the best chance of winning the race.

# Many applications for weighted shortest paths!

Obviously Orienteering is not a business application, but in logistics, planning, impact analysis and many other applications, weighted shortest path algorithms will have a great potential. Whether it is to find out how things are related to eachother, determining the most efficient way to get something from point A to point B, or finding out who would be affected by a particular type of capacity outage – the approach that I used for my orienteering problem would work just as nicely!

**Want to learn more about graph databases? Click below to get your free copy of O’Reilly’s**

*Graph Databases*ebook and discover how to use graph technologies for your application today.Download My Ebook

Keywords: graph algorithms • orienteering • shortest path • weighted shortest path

### 4 Comments

Obviously the way for me to investigate Graph Databases, and Neo4J in particular, as I too orienteer, having started out at 11 years old!

Just wanted to call this out… Using version 2.3.1

In the reduce function, I had to use ‘|’ instead of ‘:’

Also, I did not use the START section. My code below:

MATCH p=(a:Location{name:’A’})-[:DELIVERS_TO*1..10]->(n:Location{name:’N’})

RETURN p AS shortestPath, reduce(cost=0, r in relationships(p) | cost+r.cost) AS totalCost

ORDER BY totalCost ASC

LIMIT 1

Thanks for the above example.But we need to find the shortestpath between two nodes using node property filter using Neo4j 3.0.1 java version.

What I mean shortestpath api should filter the paths based on node filter property internally and among the filtered paths , it should find the shortest path.

Kindly give me the sggestions.

### Leave a Reply

### Share your Graph Story?

Email us: content@neotechnology.com

### Have a Graph Question?

###### Reach out and connect with the Neo4j staff.

StackoverflowContact Us

### Popular Graph Topics

- cypher (166)
- graph database (152)
- graphconnect (121)
- nosql (115)
- emil eifrem (76)
- graph visualization (60)
- relational database (52)
- Graph Databases (51)
- Graph Databases (50)
- community (46)

Nice use of reduce. 🙂