Skip to main content

pareto_paths

Function pareto_paths 

Source
pub fn pareto_paths(
    from: &[usize],
    to: &[usize],
    w_cost: &[f64],
    w_res: &[f64],
    n_nodes: usize,
    source: usize,
    target: usize,
    budget: f64,
    max_routes: usize,
) -> Vec<ParetoRoute>
Expand description

Bicriteria shortest paths from source to target by label-setting (Martins’ algorithm): every edge carries a (cost, resource) pair and the result is the Pareto front of nondominated (cost, resource) path values, in increasing cost / decreasing resource order. With a finite budget the front is restricted to paths with resource <= budget, so its first entry solves the constrained shortest path problem exactly. max_routes caps the number of routes returned (usize::MAX for the whole front).

Labels are popped lexicographically by (cost, resource), which makes the per-node dominance test a single comparison against the best resource seen at that node. Reverse-Dijkstra lower bounds on the remaining resource prune labels that cannot reach the target within budget, and labels whose projected resource cannot improve on the target’s front are dropped early. Weights must be nonnegative; the search is exact.