Function astar 

pub fn astar<F>(
    graph: &Subgraph,
    start: &str,
    goal: &str,
    heuristic: F,
) -> Option<(f64, Vec<String>)>
where
    F: Fn(&str, &str) -> f64,

A* search from start to goal (§5.4).

Returns the total cost and the full path inclusive of both endpoints, or None when goal is unreachable. heuristic must be admissible — it must never overestimate the remaining cost — or the path returned is a path but not necessarily the shortest one.

This is the one algorithm here that is not on the dense view

Every other function in this module settles every node, so the O(V + E) cost of building the integer view is charged against work that is O(V + E) anyway. astar returns the moment the goal is popped, and that is the entire reason to call it rather than dijkstra. Building a whole-graph index first makes its cost independent of how far the goal is — which is not a constant factor, it is the early exit itself.

0.13.28 put it on the dense view without measuring it. D-202 measured it: on the 49,152-node fixture a one-hop goal cost 16.3 ms on the dense view and 0.019 ms here, settling six nodes either way. Distant goals go the other way — the dense view finishes them in about a fifth of the time — but a goal that is the whole graph away is a dijkstra call written as an astar, and the cost of serving it well is charging every near query for a graph it never looks at.

a_near_goal_does_not_pay_for_the_whole_graph holds this, by comparing against dijkstra on the same graph in the same test rather than against a wall-clock threshold.