How to Find All Weighted Shortest Paths Between Nodes and Do It Fast

The blog post by Bruno Sacaric explores the development and optimization of an "All Shortest Paths" algorithm for Memgraph, a platform used to analyze graphs. The focus is on finding all weighted shortest paths between nodes, accommodating scenarios where multiple paths of the same length exist. Initially, the team aimed to create a new query module within the MAGE library using the Dijkstra algorithm, optimized with parallel processing and a Fibonacci heap priority queue, resulting in a 20% performance increase. However, they shifted to integrating the algorithm directly into Memgraph's core, utilizing a cursor-based query plan to improve path ingestion efficiency. The algorithm's implementation involved addressing challenges such as setting an upper bound for search depth, ensuring it could differentiate states of visited relationships without slowing down performance. Users can employ this algorithm similarly to Memgraph’s existing Weighted Shortest Path algorithm, with the flexibility to create custom query modules using Memgraph’s C API, contributing to the MAGE library.