bmssp 0.1.0

The BMSSP algorithm
Documentation

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

Algorithm Time Complexity Space Notes
Dijkstra O(m + n log n) O(n) Classical approach
BMSSP O(m + n log² n / log log n) O(n) This implementation

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:

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.