A high-performance Go implementation of the Bounded Multi-Source Shortest Path (BMSSP) algorithm, which provides significant speedups over traditional Dijkstra's algorithm for single-source shortest path problems.
This implementation is based on the paper "Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" by Ran Duan et al. The BMSSP algorithm achieves O(m log^(2/3) n) time complexity, breaking the traditional sorting barrier for shortest path algorithms.
Our benchmarks show significant performance improvements over standard Dijkstra's algorithm:
| Graph Type | Dijkstra | BMSSP | Speedup |
|---|---|---|---|
| Random 100 nodes | 37.1ÎĽs | 22.3ÎĽs | 1.66x |
| Random 1000 nodes | 453ÎĽs | 100ÎĽs | 4.53x |
| Grid 50Ă—50 | 987ÎĽs | 180ÎĽs | 5.50x |
Performance advantages increase with graph size and are particularly pronounced on structured graphs.
go get github.com/mfreeman451/bmssp-gopackage main
import (
"fmt"
"math"
"github.com/mfreeman451/bmssp-go"
)
func main() {
// Create a new graph
g := bmssp.NewGraph()
// Add edges (u, v, weight)
g.AddEdge(0, 1, 2.0)
g.AddEdge(0, 2, 5.0)
g.AddEdge(1, 3, 4.0)
g.AddEdge(2, 3, 1.0)
// Initialize distance map
dhat := make(map[bmssp.NodeID]bmssp.Dist)
for i := 0; i < 4; i++ {
dhat[bmssp.NodeID(i)] = bmssp.Dist(math.Inf(1))
}
dhat[0] = 0 // source node
// Create source set
S := bmssp.NewNodeSet()
S.Add(0)
// Run BMSSP algorithm
bound, visited := bmssp.BMSSP(
2, // recursion levels (l)
1000, // distance bound (B)
S, // source set
100, // expansion parameter (k)
1, // branching parameter (t)
g, // graph
dhat, // distance map (modified in-place)
)
fmt.Printf("Bound: %v\n", bound)
fmt.Printf("Visited nodes: %v\n", visited)
fmt.Printf("Distances: %v\n", dhat)
}type NodeID int // Graph node identifier
type Dist float64 // Distance/weight type
type Graph struct { ... } // Directed graph structure
type NodeSet map[NodeID]struct{} // Set of nodesThe main BMSSP algorithm implementation.
Parameters:
l: Recursion depth levelsB: Distance bound for explorationS: Set of source nodesk: Expansion parameter (controls exploration breadth)t: Branching parameter (affects data structure sizing)g: Input graphdhat: Distance map (modified in-place)
Returns:
- Final bound and set of visited nodes
Bounded Dijkstra's algorithm used as the base case.
Standard Dijkstra's algorithm for comparison.
g := NewGraph() // Create new graph
g.AddEdge(u, v, weight) // Add directed edge
edges := g.OutEdges(u) // Get outgoing edges from node us := NewNodeSet() // Create new node set
s.Add(nodeID) // Add node to set
count := s.Len() // Get set size
clone := s.Clone() // Create copy of setl(levels): Start with 1-2 for most graphs. Higher values may help on very large graphs.k(expansion): Use 50-200. Higher values explore more nodes but may be slower.t(branching): Usually 1 is sufficient.B(bound): Use a large value (e.g., 1000) to explore the full graph.
// For small graphs (< 1000 nodes)
bound, visited := bmssp.BMSSP(1, 1000, sources, 50, 1, graph, distances)
// For large graphs (> 1000 nodes)
bound, visited := bmssp.BMSSP(2, 1000, sources, 100, 1, graph, distances)
// For very structured graphs (grids, trees)
bound, visited := bmssp.BMSSP(1, 1000, sources, 200, 1, graph, distances)func ExampleRandomGraph() {
g := bmssp.NewGraph()
// Create random graph
edges := [][3]float64{
{0, 1, 3}, {0, 2, 8}, {1, 2, 2}, {1, 3, 5},
{2, 4, 4}, {3, 4, 1}, {3, 5, 6}, {4, 5, 2},
}
for _, e := range edges {
g.AddEdge(bmssp.NodeID(e[0]), bmssp.NodeID(e[1]), bmssp.Dist(e[2]))
}
// Run BMSSP from node 0
dhat := initializeDistances(g, 0)
sources := bmssp.NewNodeSet()
sources.Add(0)
bmssp.BMSSP(2, 1000, sources, 100, 1, g, dhat)
// dhat now contains shortest distances from node 0
}func ExampleGridGraph() {
g := createGridGraph(10, 10) // 10x10 grid
dhat := initializeDistances(g, 0) // top-left corner
sources := bmssp.NewNodeSet()
sources.Add(0)
// BMSSP works particularly well on structured graphs
bmssp.BMSSP(1, 1000, sources, 200, 1, g, dhat)
}Run benchmarks to compare with Dijkstra:
go test -bench=. -benchmem ./...This will run comprehensive benchmarks on various graph types and sizes.
go test ./... # Run all tests
go test -v ./... # Verbose output
go test -race ./... # Race condition detectiongo test -bench=. ./... # Run all benchmarks
go test -bench=Random ./... # Random graph benchmarks
go test -bench=Grid ./... # Grid graph benchmarksGenerate documentation:
go doc -all # View all documentation
godoc -http=:6060 # Local documentation serverThe BMSSP algorithm works by:
- Finding Pivots: Identifies key nodes for exploration using
FindPivots - Hierarchical Processing: Uses recursive calls with decreasing bounds
- Bounded Exploration: Each level only explores nodes within distance bounds
- Efficient Data Structures: Custom bucketed queue (
DStruct) for fast operations
- Breaking the sorting barrier: Achieves sub-O(m log n) complexity
- Adaptive exploration: Only visits relevant parts of the graph
- Memory efficiency: Lower memory usage than traditional algorithms
- Structured graph optimization: Excellent performance on grids, trees, etc.
- Fork the repository
- Create a feature branch (
git checkout -b feature/amazing-feature) - Commit your changes (
git commit -m 'Add amazing feature') - Push to the branch (
git push origin feature/amazing-feature) - Open a Pull Request
This project is licensed under the MIT License - see the LICENSE file for details.
If you use this implementation in academic work, please cite:
@article{duan2024breaking,
title={Breaking the Sorting Barrier for Directed Single-Source Shortest Paths},
author={Duan, Ran and others},
journal={arXiv preprint arXiv:2504.17033},
year={2024}
}