This project is a Java 21 Maven implementation of the BMSSP (Bounded Multi-Source Shortest Path) algorithm, based on the provided Python/Rust reference code. The project provides both the BMSSP algorithm and a standard Dijkstra's algorithm for comparison.

• Graph generation utilities (sparse directed graphs with random edges).
• Full BMSSP recursive algorithm with base cases, pivot selection, and data structure D.
• Standard Dijkstra's Algorithm: For performance comparison
• Instrumentation: Performance tracking for relaxations and heap operations
• Randomized Test Harness: Generate and test on various graph sizes
• Maven Integration: Proper project structure with dependencies
• Java 21 Features: Modern Java syntax and features where appropriate
• Comprehensive Testing: Unit tests covering various scenarios

• Java 21 (ensure java --version reports 21)
• Maven 3.6+

Clone the repository and change directory:

git clone https://github.com/PatrickDiallo23/BMSSP-Java.git cd BMSSP-Java/bmssp-java 

Then run:

mvn clean compile

• n, --nodes <NUM>: Number of nodes (default: 200000)
• m, --edges <NUM>: Number of edges (default: 800000)
• s, --seed <NUM>: Random seed (default: 0)
• -source <NUM>: Source node (default: 0)
• h, --help: Show help message

# Run with default parameters (200k nodes, 800k edges) mvn exec:java # Run with custom parameters mvn exec:java -Dexec.args="-n 50000 -m 200000 -s 42" # See help mvn exec:java -Dexec.args="--help"

The program reports timing and statistics for both algorithms, for example:

Generating graph: n=200000, m=800000, seed=0 Graph generated. avg out-degree ≈ 4.000 Dijkstra: time=0.453019s, relaxations=800000, heap_ops=532376, reachable=200000 BMSSP params: top-level l=2 BMSSP: time=0.161213s, relaxations=25545, reachable=8363, B'=0.0, |U_final|=2048 Distance agreement (max abs diff on commonly reachable nodes): 6.111340e+01 

• Dijkstra stats: runtime, relaxations, heap operations, reachable nodes
• BMSSP stats: runtime, relaxations, reachable nodes, computed B', and final set size
• Agreement: maximum absolute difference in distances between Dijkstra and BMSSP

src/main/java/org/bmssp/algo/ ├── Main.java # Entry point ├── Dijkstra.java # Dijkstra implementation ├── BMSSP.java # Recursive BMSSP implementation ├── FindPivots.java # Pivot selection logic ├── BaseCase.java # Base case solver ├── DataStructureD.java # Specialized data structure for BMSSP ├── graph/ │ ├── Graph.java # Graph representation │ ├── GraphGenerator.java # Random sparse graph generator │ └── Edge.java # Immutable edge class └── util/ └── Instrument.java # Counters for relaxations & heap ops 

The BMSSP algorithm is a sophisticated shortest path algorithm that uses:

1. Recursive Structure: Divides the problem into smaller subproblems
2. Pivot Selection: Uses FIND_PIVOTS to select strategic nodes for exploration
3. Bounded Exploration: Limits search within distance bounds
4. Specialized Data Structure: Custom data structure D for efficient operations

• BMSSP: Main recursive function with depth parameter l
• FIND_PIVOTS: Bounded Bellman-Ford-like algorithm for pivot selection
• BASECASE: Dijkstra-like expansion for small problems
• DataStructure D (Partial Queue): Supports insert, batch_prepend, and pull operations

The algorithm automatically chooses parameters based on graph size:

• t ≈ (log n)^(2/3): Controls recursion branching
• k ≈ (log n)^(1/3): Limits exploration depth
• l: Recursion depth, chosen heuristically

The implementation includes comprehensive instrumentation to track:

• Number of edge relaxations
• Heap operations
• Execution time
• Distance accuracy compared to Dijkstra

The project includes comprehensive tests:

• Unit tests for individual components
• Integration tests comparing BMSSP vs Dijkstra
• Random graph generation and testing
• Edge cases (single node, disconnected graphs)

Run specific tests:

# Run all tests mvn test # Run a specific test mvn test -Dtest=BMSSPTest#testSimpleGraph 

bash

• For small graphs (n < 1000), Dijkstra is typically faster due to overhead
• For large sparse graphs, BMSSP may show theoretical advantages
• Performance depends heavily on graph structure and parameter tuning
• The implementation prioritizes correctness and clarity over micro-optimizations

• This is inspired from the existing Python implementation of the algorithm, Rust implementation, and a Medium article.
• Designed for research/educational use, not optimized for production-scale shortest paths (yet).
• BMSSP recursion parameters (l) are automatically chosen based on n.
• You may need to adjust JVM memory settings (-Xmx4g or higher) for very large graphs.
• You are free to contribute to this repository.

MIT License (free to use, modify, and distribute).