BMSSP - Breaking the Sorting Barrier for Single-Source Shortest Paths

A Rust implementation of the groundbreaking BMSSP (Bounded Multi-Source Shortest Path) algorithm from the paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" by R. Duan, J. Mao, X. Mao, X. Shu, and L. Yin.

Overview

This library implements the first algorithm to achieve a sub-quadratic time complexity for the single-source shortest path problem on directed graphs, breaking the long-standing "sorting barrier" that has limited performance since Dijkstra's algorithm.

Key Achievements

• Time Complexity: O(m + n log² n / log log n) for graphs with non-negative edge weights
• Breaking the Sorting Barrier: First algorithm to achieve better than O(m + n log n) complexity
• Theoretical Breakthrough: Represents a major advancement in algorithmic graph theory after decades of research

Algorithm Description

The BMSSP algorithm uses a recursive divide-and-conquer approach with three main components:

1. Find Pivots (Algorithm 1): Identifies key vertices to partition the problem space
2. Base Case (Algorithm 2): Handles small subproblems using a modified Dijkstra approach
3. BMSSP (Algorithm 3): The main recursive algorithm that coordinates the solution

Core Innovation

Instead of maintaining a single global priority queue like Dijkstra's algorithm, BMSSP:

• Recursively partitions the problem into bounded subproblems
• Uses specialized data structures to efficiently manage multiple search frontiers
• Achieves better complexity through careful control of recursion depth and problem size

Installation

Add this to your Cargo.toml:

cargo add bmssp

Usage

use bmssp::{ShortestPath, Graph, Edge};

// Create a graph
let mut graph = vec![Vec::new(); 4];
graph[0].push(Edge::new(1, 1.0));
graph[0].push(Edge::new(2, 4.0));
graph[1].push(Edge::new(2, 2.0));
graph[1].push(Edge::new(3, 5.0));
graph[2].push(Edge::new(3, 1.0));

// Initialize the shortest path solver
let mut sp = ShortestPath::new(graph);

// Compute shortest paths from vertex 0
let distances = sp.get(0);

// distances[i] now contains the shortest distance from vertex 0 to vertex i
println!("Distance to vertex 1: {}", distances[1]); // Output: 1.0
println!("Distance to vertex 2: {}", distances[2]); // Output: 3.0
println!("Distance to vertex 3: {}", distances[3]); // Output: 4.0

Performance Characteristics

The algorithm's performance depends on graph structure:

• Sparse Graphs: Most significant improvements over Dijkstra
• Dense Graphs: Benefits become more pronounced with larger graph sizes
• Real-world Networks: Excellent performance on typical network topologies

Complexity Analysis

• Time: O(m + n log² n / log log n)
• Space: O(n + m)
• Recursion Depth: O(log n)

Where:

• n = number of vertices
• m = number of edges

Testing

You can check the example:

cargo run --example simple

Run the test suite:

cargo test

The implementation is verified against the AOJ GRL_1_A test cases to ensure correctness.

Benchmarking

Run benchmarks with different type of graphs

cargo bench --bench bench_bmssp

If you want to profile the functions you can use

cargo bench --bench bench_bmssp -- --profile-time=30

Comparison with Classical Algorithms

Development

Building from Source

git clone https://github.com/your-username/bmssp
cd bmssp
cargo build --release

With Nix

This project includes a Nix flake for reproducible builds:

nix develop  # Enter development shell
cargo build

Theoretical Background

The algorithm addresses fundamental limitations in shortest path computation:

1. The Sorting Barrier: Previous algorithms were limited by the O(n log n) sorting complexity
2. Recursive Decomposition: Breaks the problem into geometrically decreasing subproblems
3. Bounded Search: Each recursive call operates within carefully computed distance bounds

Limitations and Future Work

• Currently implements the basic algorithm without advanced optimizations
• The BlockHeap uses a simplified implementation (BTreeSet) rather than the specialized data structure from Lemma 3.3
• Performance gains should be most noticeable on very large graphs
• Make it more idiomatic
• Add more tests
• Add comparaisons

Contributing

Contributions are welcome! Areas for improvement:

• Implement the specialized data structure from Lemma 3.3
• Optimize memory usage and constant factors
• Add parallel processing capabilities

Architecture

The library is organized into several key modules:

• models.rs: Core data types (Vertex, Length, Edge, Graph)
• heaps.rs: Priority queue implementations (Heap, BlockHeap)
• shortest_path.rs: Main BMSSP algorithm implementation (ShortestPath)

Core Algorithm Flow

1. Initialization: The ShortestPath::get method sets up parameters and calls the main algorithm
2. Recursive Decomposition: ShortestPath::bmssp recursively breaks down the problem
3. Pivot Selection: ShortestPath::find_pivots identifies key vertices for partitioning
4. Base Case: ShortestPath::base_case handles small subproblems with a modified Dijkstra approach

License

Licensed under the Apache License, Version 2.0. See LICENSE for details.