This blog series is designed to help you better utilize graph analytics and graph algorithms so you can effectively innovate and develop intelligent solutions faster using a graph database.

Last week we began our look at pathfinding and graph search algorithms, starting with the Shortest Path algorithm. This week we’ll look at the Single Source Shortest Path algorithm, which calculates a path between a node and all other nodes whose summed value (weight of relationships such as cost, distance, time or capacity) to all other nodes is minimal.

Single Source Shortest Path is faster than Shortest Path and is used for the same types of problems. It is also essential in logical routing such as telephone call routing.

### About Single Source Shortest Path

The Single Source Shortest Path (SSSP) algorithm calculates the shortest (weighted) path from a node to all other nodes in the graph.

SSSP came into prominence at the same time as the Shortest Path algorithm and Dijkstra’s algorithm acts as an implementation for both problems.

Neo4j implements a variation of SSSP, the delta-stepping algorithm. The delta-stepping algorithm outperforms Dijkstra’s and efficiently works in sequential and parallel settings for many types of graphs.

### When Should I Use Single Source Shortest Path?

Open Shortest Path First is a routing protocol for IP networks. It uses Dijkstra’s algorithm to help detect changes in topology, such as link failures, and come up with a new routing structure in seconds.

TIP:Delta-stepping does not support negative weights. The algorithm assumes that adding a relationship to a path never makes a path shorter – an invariant that would be violated with negative weights.

### Single Source Shortest Path Example

Let’s calculate Single Source Shortest Path on a small dataset.

The following Cypher statement creates a sample graph containing locations and connections between them.

`MERGE (a:Loc {name:"A"})`

MERGE (b:Loc {name:"B"})

MERGE (c:Loc {name:"C"})

MERGE (d:Loc {name:"D"})

MERGE (e:Loc {name:"E"})

MERGE (f:Loc {name:"F"})

MERGE (a)-[:ROAD {cost:50}]->(b)

MERGE (a)-[:ROAD {cost:50}]->(c)

MERGE (a)-[:ROAD {cost:100}]->(d)

MERGE (b)-[:ROAD {cost:40}]->(d)

MERGE (c)-[:ROAD {cost:40}]->(d)

MERGE (c)-[:ROAD {cost:80}]->(e)

MERGE (d)-[:ROAD {cost:30}]->(e)

MERGE (d)-[:ROAD {cost:80}]->(f)

MERGE (e)-[:ROAD {cost:40}]->(f);

Now we can run the Single Source Shortest Path algorithm to find the shortest path between A and all other nodes. Execute the following query.

`MATCH (n:Loc {name:"A"})`

CALL algo.shortestPath.deltaStepping.stream(n, "cost", 3.0

YIELD nodeId, distance

MATCH (destination) WHERE id(destination) = nodeId

RETURN destination.name AS destination, distance

The above table shows the cost of going from

`A`

to each of the other nodes, including itself at a cost of 0.### Conclusion

We’ve covered the second in our list of pathfinding algorithms, Single Source Shortest Path. Next week we’ll have a look at another pathfinding algorithm, All Pairs Shortest Path, which calculates the shortest (weighted) path between all pairs of nodes.

**Find the patterns in your connected data**

Learn about the power of graph algorithms in this ebook,

Learn about the power of graph algorithms in this ebook,

*A Comprehensive Guide to Graph Algorithms in Neo4j*. Click below to get your free copy.Read the Ebook

Explore: cypher • Dijkstra's algorithm • graph algorithms • Graph Analytics • Graph Search • Open Shortest Path First • pathfinding • shortest path • Single Source Shortest Path • telecom

#### About the Author

### Mark Needham & Amy E. Hodler , Neo4j

Mark Needham is a Support Engineer for Neo4j. He also blogs about software development at markhneedham.com.

Amy is the Analytics and AI Program Manager at Neo4j. She believes a thriving graph ecosystem is essential to catalyze new types of insights. Accordingly, she helps ensure Neo4j partners are successful. In her career, Amy has consistently helped teams break into new markets at startups and large companies including EDS, Microsoft, and Hewlett-Packard (HP). She most recently comes from Cray Inc., where she was the analytics and artificial intelligence market manager.Amy has a love for science and art with an extreme fascination for complexity science and graph theory. When the weather is good, you’re likely to find her cycling the passes in beautiful Eastern Washington.

### Upcoming Event

### Have a Graph Question?

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

Stack OverflowCommunity Forums

Contact Us

### Share your Graph Story?

Email us: content@neo4j.com

## Leave a Reply