sssp-lib

A Rust library for Single Source Shortest Path (SSSP) algorithms in graphs.

This crate provides an efficient implementation of SSSP using a bounded-memory shortest path algorithm, suitable for large graphs with constraints on memory and computation.

Installation

Add this to your Cargo.toml:

[dependencies]
sssp-lib = "0.1.0"

Usage

Basic Example

use sssp_lib::SSSPAlgorithm;

fn main() {
    // Create a new algorithm instance with 5 nodes
    let mut algo = SSSPAlgorithm::new(5);

    // Add some edges
    algo.graph.add_edge(0, 1, 1.0);
    algo.graph.add_edge(1, 2, 2.0);
    algo.graph.add_edge(2, 3, 1.0);
    algo.graph.add_edge(0, 3, 4.0);

    // Run SSSP from node 0
    let distances = algo.run(0);

    // Print distances
    for (node, dist) in distances {
        println!("Distance to node {}: {}", node, dist);
    }
}

Generating Random Graphs for Testing

use sssp_lib::SSSPAlgorithm;

fn main() {
    // Generate a large random graph with 1000 nodes, 5 edges per node
    let algo = SSSPAlgorithm::generate_large_random(1000, 5);

    // Run SSSP
    let distances = algo.run(0);
    println!("Reached {} nodes", distances.len());
}

Documentation

Full API documentation is available at docs.rs/sssp-lib.

License

Licensed under the Apache License, Version 2.0. See LICENSE for details.

Contributing

Contributions are welcome! Please open an issue or submit a pull request.