Skip to main content

shortest_path

reddb_server::storage::engine::graph_algorithms

Function shortest_path 

Source 
pub fn shortest_path<N: Clone + Ord>(
    nodes: &[N],
    edges: &[(N, N, Weight)],
    src: &N,
    dst: &N,
    max_hops: Option<usize>,
) -> Option<Vec<(N, f64)>>
Expand description

Single-source single-target shortest path over an abstract undirected weighted graph.

Inputs mirror connected_components / louvain:

  • nodes: the declared node universe.
  • edges: weighted edges (src, dst, weight), treated as UNDIRECTED. Endpoints not present in nodes are still included in the universe. Parallel edges between the same pair collapse to their MINIMUM weight; self-loops are ignored (they never shorten a path). Edge weights are assumed NON-NEGATIVE (the storage layer’s f32 weights are); the shortest-path / triangle-inequality guarantees below hold under that assumption.
  • src, dst: the path endpoints. Either absent from the universe yields None.
  • max_hops: an optional cap on the number of EDGES in the path. None means unbounded. The result is the minimum-weight path using at most max_hops edges; if no such path exists, None.

Output: Some(path) where path is the ordered sequence of (node, cumulative_weight) from src to dst (the first entry is (src, 0.0), the hop index is the position in the vector, and the last entry’s weight is the total path weight). None when dst is unreachable from src (within the hop budget) — the executor maps this to an EMPTY result set, never an error. A zero-length path (src == dst) returns the single entry (src, 0.0).

Algorithm: a hop-limited Bellman-Ford relaxation. Each round relaxes every (undirected) edge against the previous round’s distances, so after k rounds dist[v] is the shortest distance to v using at most k edges. With max_hops = None we run n - 1 rounds, which suffices for the true shortest path because — with non-negative weights — a shortest path is simple and therefore uses at most n - 1 edges. O(rounds · E).

Determinism (guaranteed and tested): the node universe is a sorted, deduped BTreeSet giving stable indices; relaxation sweeps nodes in index order and neighbours in ascending index order; ties keep the lower-index predecessor. Identical (nodes, edges, src, dst, max_hops) always produces identical output. On an undirected graph the distance is symmetric: shortest_path(.., a, b, ..) and shortest_path(.., b, a, ..) have equal total weight.