sssp

🚀 SSSP

An official TypeScript implementation of the breakthrough algorithm from “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths” 🏆

This algorithm beats the classic O(m log n) bound of Dijkstra, achieving sub-sorting complexity for the Single-Source Shortest Paths (SSSP) problem.

✨ Overview

This implementation showcases the key innovation from the research: Randomized Bucketing 🪣 instead of exact priority queues.

This clever trick breaks the long-standing sorting barrier while still guaranteeing correctness.

🔑 Key Features

• 🪣 Randomized Bucket Queue – replaces traditional priority queues with approximate ordering
• ⚡ Sub-sorting Complexity – runs faster than Dijkstra in theory & practice
• ✅ Correctness Guaranteed – always computes the true shortest paths
• 🧪 Comprehensive Tests – validated against a classical Dijkstra implementation

💡 Why Use This?

Shortest paths are everywhere, and performance matters. This package gives researchers, engineers, and hobbyists access to the first practical algorithm that outperforms Dijkstra’s theoretical limit.

Some applications:

• 🌐 Networking & Routing: Faster route computation in large communication networks
• 🚗 Transportation & Logistics: Real-time pathfinding for traffic, navigation, supply chain
• 🧮 Graph Machine Learning: Efficient preprocessing on massive graph datasets
• 🎮 Game Development: Optimized pathfinding in large game maps or AI systems
• 🏢 Research & Teaching: A modern, cutting-edge SSSP algorithm for students and academics

🧠 Algorithm Innovation

Traditional Dijkstra

1️⃣ Extract min-distance vertex (heavy sorting step) 2️⃣ Relax edges 3️⃣ Update priority queue (sorting again)

New Approach — Randomized Bucketing 🎲

1️⃣ Group vertices into distance-range buckets 2️⃣ Process entire buckets in approximate order 3️⃣ Use randomization to control “out-of-order” work 4️⃣ Apply local corrections to ensure correctness

🧩 Core Components

RandomizedBucketQueue

• Groups vertices into distance buckets
• Uses random perturbations for tie-breaking
• Efficiently processes by ranges instead of exact order

SSSPSolver

• Main algorithm engine ⚙️
• Relaxes edges using the bucket-based approach
• Guarantees correctness despite approximate ordering

ClassicalDijkstra

• Standard reference implementation
• Used for testing & validation

🔧 Usage

import { SSSPSolver, createGraph } from "sssp";

// Create a graph: vertices 0,1,2 with edges
const graph = createGraph(3, [
  [0, 1, 4], // Edge from 0 to 1 with weight 4
  [0, 2, 2], // Edge from 0 to 2 with weight 2
  [1, 2, 1], // Edge from 1 to 2 with weight 1
]);

const solver = new SSSPSolver(graph);
const result = solver.solve(0); // Find shortest paths from vertex 0

console.log("Distances:", result.distances);
// [0, 4, 2]

console.log("Predecessors:", result.predecessors);
// [null, 0, 0]

// Get a path to vertex 2
const pathTo2 = solver.getPath(2); // [0, 2]

📖 Reference

📄 Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (arXiv)

🌟 Install now:

npm install sssp