DZone
Database Zone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
  • Refcardz
  • Trend Reports
  • Webinars
  • Zones
  • |
    • Agile
    • AI
    • Big Data
    • Cloud
    • Database
    • DevOps
    • Integration
    • IoT
    • Java
    • Microservices
    • Open Source
    • Performance
    • Security
    • Web Dev
DZone > Database Zone > Graph Algorithms in Neo4j: All Pairs Shortest Path

Graph Algorithms in Neo4j: All Pairs Shortest Path

Look at the cousin of the Single Path Shortest Path algorithm.

Amy Hodler user avatar by
Amy Hodler
·
Mark Needham user avatar by
Mark Needham
·
Jan. 14, 19 · Database Zone · Tutorial
Like (2)
Save
Tweet
5.69K Views

Join the DZone community and get the full member experience.

Join For Free

Graph algorithms provide the means to understand, model, and predict complicated dynamics such as the flow of resources or information, the pathways through which contagions or network failures spread, and the influences on and resiliency of groups.

This 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 time, we took our second look at pathfinding and graph search algorithms with a focus on the Single Source Shortest Path algorithm, using examples from Neo4j.

This time, we will examine another of these algorithms with a look at the All Pairs Shortest Path algorithm, which is used to evaluate alternate routes for situations such as a freeway backup or network capacity. It's also key in logical routing to offer multiple paths, for example, call routing alternatives in case of a failure.

Image title

About All Pairs Shortest Path

The All Pairs Shortest Path (APSP) algorithm calculates the shortest (weighted) path between all pairs of nodes. This algorithm has optimizations that make it quicker than calling the Single Source Shortest Path algorithm for every pair of nodes in the graph.

Some pairs of nodes might not be reachable from each other, so no shortest path exists between these pairs. In this scenario, the algorithm returns infinity value as a result between these pairs of nodes.

When Should I Use All Pairs Shortest Path?

    • The All Pairs Shortest Path algorithm is used in urban service system problems, such as the location of urban facilities or the distribution or delivery of goods. One example of this is determining the traffic load expected on different segments of a transportation grid. For more information, see Urban Operations Research.
    • All Pairs Shortest Path is used as part of the REWIRE data center design algorithm, which finds a network with maximum bandwidth and minimal latency. There are more details about this approach in the following academic paper: "REWIRE: An Optimization-based Framework for Data Center Network Design."

All Pairs Shortest Path Example

Let's calculate All Pairs 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 run the All Pairs Shortest Path algorithm to find the shortest path between every pair of nodes. Execute the following query.

CALL algo.allShortestPaths.stream("cost",{nodeQuery:"Loc",defaultValue:1.0})
YIELD sourceNodeId, targetNodeId, distance
WITH sourceNodeId, targetNodeId, distance
WHERE algo.isFinite(distance) = true
MATCH (source:Loc) WHERE id(source) = sourceNodeId
MATCH (target:Loc) WHERE id(target) = targetNodeId
WITH source, target, distance WHERE source <> target
RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC
LIMIT 10

This query returned the top 10 pairs of nodes that are the furthest away from each other. F and E appear to be the most distant from the others.

Conclusion

For the past few weeks, we've covered a few use cases with our look at pathfinding and graph search algorithms, including this week's look at All Pairs Shortest Path.

Next time, we will continue our examination of these types of algorithms with an overview of the Minimum Weight Spanning Tree algorithm, which calculates the paths along a connected tree structure with the smallest value (weight of the relationship such as cost, time or capacity) associated with visiting all nodes in the tree.

Algorithm Graph (Unix) Neo4j

Published at DZone with permission of Amy Hodler, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Snake-Based REST API (Python, Mamba, Hydra, and Fast API)
  • Tools and Integrations to Significantly Improve Code Review in GitHub
  • Working With Geospatial Data in Redis
  • SRE: From Theory to Practice: What’s Difficult About Tech Debt?

Comments

Database Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • MVB Program
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends:

DZone.com is powered by 

AnswerHub logo