Struct SSSPGraph 

pub struct SSSPGraph {
    pub adj: Vec<Vec<Edge>>,
    pub n: usize,
}

Represents a graph for SSSP algorithms.

The graph is stored as an adjacency list.

Fields

adj: Vec<Vec<Edge>>

Adjacency list: adj[u] contains edges from node u.

n: usize

Number of nodes in the graph.

Implementations

impl SSSPGraph

pub fn new(n: usize) -> Self

Creates a new empty graph with n nodes.

Arguments

• n - The number of nodes.

Examples

use sssp_lib::graph::SSSPGraph;

let graph = SSSPGraph::new(5);

pub fn add_edge(&mut self, u: usize, v: usize, w: f64)

Adds a directed edge from node u to node v with weight w.

If u or v is out of bounds, the edge is ignored.

Arguments

• u - The source node index.
• v - The target node index.
• w - The edge weight.

Examples

use sssp_lib::graph::SSSPGraph;

let mut graph = SSSPGraph::new(3);
graph.add_edge(0, 1, 1.0);

pub fn bmssp( &self, sources: Vec<(usize, f64)>, b_bound: f64, u_bound: usize, ) -> (HashMap<usize, f64>, HashMap<usize, usize>)

Runs the Bounded Memory Shortest Path (BMSSP) algorithm.

This is an internal method used by the SSSP algorithm with bounds on distance and work.

Arguments

• sources - A vector of (node, initial_distance) pairs.
• b_bound - The maximum distance bound.
• u_bound - The maximum work bound (number of relaxations).

Returns

A tuple of (distances, parents) HashMaps.