Neo4j Shortest Path and Dijkstra Algorithms
May 8: Hero City, One Month Graph Challenge
Welcome word
In this series of small posts I do one simple graph daily. Domain model of graph somehow related to day’s history, some historical event, celebration or person. I do this challenge to learn Neo4j Data Modeling and Cypher. Every day. One month. Follow me. Maybe you will be inspired and next month would be yours One Month Graph Challenge. #OMGChallenge
Domain model
In 1965, 8 of May USSR government approved the Regulations on the honorary title “Hero City”. This title is conferred to the cities of the Soviet Union, whose residents displayed mass heroism and courage in defending the Homeland in the World War II of 1941–1945 (Eastern Front). This honor title is carried by 13 cities (one of which is a Hero Fortress in Brest, city of Belarus).
Today I want continue learn Cypher. I plan to build up a small graph of Hero Cities and apply path-finding query on it.
Graph
Create Hero Cities with connections to the nearest cities in both directions.
MERGE (b:Hero:Fortress { name: "Brest Fortress" })
MERGE (l:Hero:City { name: "Leningrad" })
MERGE (v:Hero:City { name: "Volgograd" })
MERGE (o:Hero:City { name: "Odessa" })
MERGE (s:Hero:City { name: "Sevastopol" })
MERGE (moscow:Hero:City { name: "Moscow" })
MERGE (k:Hero:City { name: "Kiev" })
MERGE (n:Hero:City { name: "Novorossiysk" })
MERGE (kerch:Hero:City { name: "Kerch" })
MERGE (minsk:Hero:City { name: "Minsk" })
MERGE (t:Hero:City { name: "Tula" })
MERGE (m:Hero:City { name: "Murmansk" })
MERGE (smolensk:Hero:City { name: "Smolensk" })
MERGE (m)-[:CONNECTED_TO { distance: 1013 }]->(l)-[:CONNECTED_TO { distance: 1013 }]->(m)
MERGE (l)-[:CONNECTED_TO { distance: 692 }]->(minsk)-[:CONNECTED_TO { distance: 692 }]->(l)
MERGE (l)-[:CONNECTED_TO { distance: 634 }]->(moscow)-[:CONNECTED_TO { distance: 634 }]->(l)
MERGE (l)-[:CONNECTED_TO { distance: 583 }]->(smolensk)-[:CONNECTED_TO { distance: 583 }]->(l)
MERGE (smolensk)-[:CONNECTED_TO { distance: 307 }]->(minsk)-[:CONNECTED_TO { distance: 307 }]->(smolensk)
MERGE (t)-[:CONNECTED_TO { distance: 173 }]->(moscow)-[:CONNECTED_TO { distance: 173 }]->(t)
MERGE (smolensk)-[:CONNECTED_TO { distance: 369 }]->(moscow)-[:CONNECTED_TO { distance: 369 }]->(smolensk)
MERGE (b)-[:CONNECTED_TO { distance: 325 }]->(minsk)-[:CONNECTED_TO { distance: 325 }]->(b)
MERGE (k)-[:CONNECTED_TO { distance: 434 }]->(minsk)-[:CONNECTED_TO { distance: 434 }]->(k)
MERGE (k)-[:CONNECTED_TO { distance: 508 }]->(b)-[:CONNECTED_TO { distance: 508 }]->(k)
MERGE (t)-[:CONNECTED_TO { distance: 365 }]->(smolensk)-[:CONNECTED_TO { distance: 365 }]->(t)
MERGE (k)-[:CONNECTED_TO { distance: 442 }]->(o)-[:CONNECTED_TO { distance: 442 }]->(k)
MERGE (s)-[:CONNECTED_TO { distance: 308 }]->(o)-[:CONNECTED_TO { distance: 308 }]->(s)
MERGE (kerch)-[:CONNECTED_TO { distance: 462 }]->(o)-[:CONNECTED_TO { distance: 462 }]->(kerch)
MERGE (kerch)-[:CONNECTED_TO { distance: 247 }]->(s)-[:CONNECTED_TO { distance: 247 }]->(kerch)
MERGE (kerch)-[:CONNECTED_TO { distance: 124 }]->(n)-[:CONNECTED_TO { distance: 124 }]->(kerch)
MERGE (v)-[:CONNECTED_TO { distance: 714 }]->(kerch)-[:CONNECTED_TO { distance: 714 }]->(v)
MERGE (v)-[:CONNECTED_TO { distance: 678 }]->(n)-[:CONNECTED_TO { distance: 678 }]->(v)
MERGE (v)-[:CONNECTED_TO { distance: 774 }]->(t)-[:CONNECTED_TO { distance: 774 }]->(v)
Nodes represent the cities and located accordingly, not exactly like on the picture, but I did my best. Now let’s try to find shortest path from Brest Hero Fortness to Hero City Volgograd:
MATCH (c1:Hero { name: 'Brest Fortress' })
MATCH (c2:City { name: 'Volgograd' })
MATCH path = shortestPath((c1)-[*]-(c2))
RETURN path
Result is ok. We asked Cypher to find shortest path by connected nodes. So it is just 2 nodes in between, result is true, can not be shorter than this. At the same time, we say nothing about actual distance between cities. And if we want to calculate shortest path with usage of distance, then it’s a different story. APOC comes here again. We need to set a start and end nodes, relationships type and property to use as a cost/weight of relationships. This is it:
MATCH (c1:Hero { name: 'Brest Fortress' })
MATCH (c2:City { name: 'Volgograd' })
CALL apoc.algo.dijkstra(c1, c2, 'CONNECTED_TO', 'distance') YIELD path, weight
RETURN path, weight
Now we got absolutely different result. With result list of nodes we also got the total “cost” of the trip, total distance between Brest and Volgograd by my graph settings is 1771 km. I am excited.
Resume
Topic of path-finding algorithms is very cool, and I want to learn with it more in upcoming posts. This is the true power of graphs. But my daily post is too short to cover more than this small stuff. Hope you have some time and ideas to play more on this Hero Cities domain. Also, I hope it was fun. Cheers!
Similar topics
Neo4j graph Data Modeling of Star Wars Universe with APOC load json
Simple example of N-ary relationship to understand basics of Neo4j Graph Data Modeling
Initial Neo4j Graph Data Modeling of Train Ticket Booking System
Unusual use of Neo4j Common Neighbors Algorithm on people community graph
Apply Neo4j Similarity Algorithm to analyse Chess “openings”
Build a Neo4j Graph of Moscow Metro Map with Spatial Values and Shortest Path Algorithm
