Function run

nodedb/src/engine/graph/algo/sssp.rs:26–92

Run SSSP (Dijkstra) from a source node on the CSR index. Returns `(node_id, distance)` for all reachable nodes. Unreachable nodes get `f64::INFINITY`. Returns an error if the source node doesn't exist.

(csr: &CsrIndex, params: &AlgoParams)

/// Returns `(node_id, distance)` for all reachable nodes. Unreachable nodes
/// get `f64::INFINITY`. Returns an error if the source node doesn't exist.
pub fn run(csr: &CsrIndex, params: &AlgoParams) -> Result<AlgoResultBatch, crate::Error> {
    let n = csr.node_count();
    if n == 0 {
        return Ok(AlgoResultBatch::new(GraphAlgorithm::Sssp));
    }

    let source = params
        .source_node
        .as_deref()
        .ok_or_else(|| crate::Error::BadRequest {
            detail: "SSSP requires source_node parameter".into(),
        })?;

    let source_id = csr
        .node_id_raw(source)
        .ok_or_else(|| crate::Error::BadRequest {
            detail: format!("source node '{source}' not found in graph"),
        })?;

    // Dijkstra requires non-negative edge weights. Pre-scan for negatives
    // to fail fast with a clear error rather than silently producing wrong results.
    if csr.has_weights() {
        for node in 0..n {
            for (_lid, _dst, w) in csr.iter_out_edges_weighted_raw(node as u32) {
                if w < 0.0 {
                    return Err(crate::Error::BadRequest {
                        detail: format!(
                            "SSSP (Dijkstra) requires non-negative edge weights, found {w} on edge from '{}'",
                            csr.node_name_raw(node as u32)
                        ),
                    });
                }
            }
        }
    }

    let mut dist = vec![f64::INFINITY; n];
    dist[source_id as usize] = 0.0;

    // Min-heap: (Reverse(distance), node_id).
    // Reverse wraps f64 for min-heap behavior with Rust's max-heap BinaryHeap.
    let mut heap: BinaryHeap<Reverse<(OrdF64, u32)>> = BinaryHeap::new();
    heap.push(Reverse((OrdF64(0.0), source_id)));

    while let Some(Reverse((OrdF64(d), u))) = heap.pop() {
        // Skip stale entries (lazy deletion).
        if d > dist[u as usize] {
            continue;
        }

        // Relax outbound edges.
        for (_lid, v, weight) in csr.iter_out_edges_weighted_raw(u) {
            let new_dist = d + weight;
            if new_dist < dist[v as usize] {
                dist[v as usize] = new_dist;
                heap.push(Reverse((OrdF64(new_dist), v)));
            }
        }