The focus of this blog post is to introduce Yen’s k-shortest path algorithm that was recently added to Neo4j graph algorithms. I will use Californian road network dataset made available by Feifei Li.

Next we will enrich our graph using Google’s reverse geocoding API and then proceed to find the shortest path with Dijkstra algorithm and the second shortest path using Yen’s k-shortest algorithm.

### Graph schema

Our graph has a simple schema of nodes labeled **Intersection** connected with relationship **CONNECTION** to other intersections.

## Import

Lets first define the constraint in our graph schema.

`CREATE CONSTRAINT ON (i:Intersection) ASSERT i.id IS UNIQUE;`

Dataset is split into nodes and relationship files. Lets import them both to get all the data we need.

#### Import nodes

USING PERIODIC COMMIT LOAD CSV FROM "https://www.cs.utah.edu/~lifeifei/research/tpq/cal.cnode" as row fieldterminator " " MERGE (i:Intersection{id:row[0]}) ON CREATE SET i.longitude = toFloat(row[1]), i.latitude = toFloat(row[2])

#### Import relationships

USING PERIODIC COMMIT LOAD CSV FROM "https://www.cs.utah.edu/~lifeifei/research/tpq/cal.cedge" as row fieldterminator " " MATCH (start:Intersection{id:row[1]}) MATCH (end:Intersection{id:row[2]}) MERGE (start)-[c:CONNECTION{id:row[0]}]->(end) ON CREATE SET c.length = toFloat(row[3])

## Reverse geocode API

For every intersection in our graph we can get the address based on the GPS location with the help of Google’s reverse geocoding API . I used `apoc.util.sleep(50)`

to throttle and wait 50 ms between each API call. It cost me around €7 to get this data as I couldn’t find a free version of the API .

MATCH (i:Intersection) CALL apoc.util.sleep(50) WITH "https://maps.googleapis.com/maps/api/geocode/json?latlng=" + toString(i.latitude) + "," + toString(i.longitude) + "&key={google_api_key}" as json,i CALL apoc.load.json(json) yield value SET i.name = value.results[0].formatted_address

## Analysis

Lets start with visualizing Santa Barbara’s part of the road network with neovis.js.

##### Neovis configuration

var config = { container_id: "viz", server_url: "bolt://localhost:7687", server_user: "neo4j", server_password: "neo4j", labels: { "Intersection": { "caption": "title" } }, relationships: { "CONNECTION": { "caption": false } }, initial_cypher: "MATCH p=(i1:Intersection)-[:CONNECTION]->(i2:Intersection)" + "WHERE i1.name contains 'Santa Barbara' AND i2.name contains 'Santa Barbara'" + "RETURN p limit 500" };

### Shortest path

We use `algo.shortestPath`

, that uses Dijkstra algorithm, to find the shortest path between “Cathedral Peak Trail” and “5750 Stagecoach Rd”. We set `direction:BOTH`

to treat our graph as undirected.

MATCH (start:Intersection{title:"Cathedral Peak Trail"}), (end:Intersection{title:"5750 Stagecoach Rd"}) CALL algo.shortestPath.stream(start,end,'length',{direction:'BOTH'}) YIELD nodeId,cost MATCH (n) where id(n)= nodeId RETURN n.title,cost

Visualization made with neovis.js.

##### Neovis configuration

var config = { container_id: "viz", server_url: "bolt://localhost:7687", server_user: "neo4j", server_password: "neo4j", labels: { "Intersection": { "caption": "title" } }, relationships: { "CONNECTION": { "thickness": "length", "caption": false } }, initial_cypher: "MATCH (start:Intersection{title:'Cathedral Peak Trail'}),(end:Intersection{title:'5750 Stagecoach Rd'}) " + "CALL algo.shortestPath.stream(start,end,'length',{direction:'BOTH',nodeQuery:'Intersection',relationshipQuery:'CONNECTION'}) YIELD nodeId,cost " + "MATCH (n) where id(n)=nodeId " + "WITH collect(n) as nodes " + "UNWIND range(0, length(nodes)-2) as index " + "WITH nodes[index] as from, nodes[index + 1] as to " + "MATCH p=(from)-[:CONNECTION]-(to) " + "RETURN p" };

### Yen’s k-shortest paths

Yen’s k-shortest paths algorithm computes single-source K-shortest loopless paths for a graph with non-negative relationship weights.

It uses Dijkstra algorithm to find the shortest path and then proceeds to find k-1 deviations of the shortest paths. If we want to find the second shortest path we use `k=2`

as shown below.

MATCH (start:Intersection{title:"Cathedral Peak Trail"}), (end:Intersection{title:"5750 Stagecoach Rd"}) CALL algo.kShortestPaths(start, end, 2, 'length' ,{}) YIELD resultCount RETURN resultCount

Results are stored as paths in our graph.

MATCH p=()-[:PATH_0|:PATH_1]->() RETURN p

Shortest path is visualized in red and second shortest path in yellow. We can easily observe that the paths diverge right at the start and join together 2 hops before the end.

## Conclusion

With the addition of Yen’s k-shortest algorithm to the Neo4j graph algorithms library we can now search for alternative shortest routes in our graph. This can come in handy in various domains.