← Back to Projects
Breaking the Sorting Barrier for Directed SSSP
Mentored by: Next Silicon
Novel algorithm for single-source shortest path computation in directed graphs
C++
Graph Algorithms
Data Structures
Parallel Computing
Benchmarking
Description
A breakthrough algorithm that improves upon traditional approaches for computing single-source shortest paths (SSSP) in directed graphs. Eliminates the need for sorting operations, significantly reducing computational complexity. Includes theoretical analysis, implementation optimizations, and performance benchmarks demonstrating superior scalability.
Team Members
Cohort: Embedded Systems Bootcamp 2025 (Embedded)
Responsibilities:
Followed standard development practices, including professional code reviews and version control with Git.
Developed high-performance C++ code using modern C++17 practices and clean, maintainable architecture.
Implemented unit tests using Google Test to ensure code correctness and reliability.
Ran performance benchmarks using Google Benchmark to evaluate runtime efficiency and compare DSSSP results against LEMON’s Dijkstra implementation.
Profiled system performance with Intel VTune to identify memory stalls and algorithmic bottlenecks.
Implemented multi-threaded execution using OpenMP and atomic CAS operations to improve performance across multiple threads.
Built automated CI workflows with GitHub Actions to maintain code stability, ensure correctness, and verify performance on every commit.
...and more contributions not listed here