Function astar_search 

pub fn astar_search<N, E, Ix, H>(
    graph: &Graph<N, E, Ix>,
    source: &N,
    target: &N,
    heuristic: H,
) -> Result<AStarResult<N, E>>
where
    N: Node + Debug + Clone + Hash + Eq,
    E: EdgeWeight + Clone + Add<Output = E> + Zero + PartialOrd + Copy,
    Ix: IndexType,
    H: Fn(&N) -> E,

A* search algorithm for finding the shortest path with a heuristic

Arguments

• graph - The graph to search
• source - Source node
• target - Target node
• heuristic - Heuristic function that estimates distance from a node to the target

Returns

• Result<AStarResult> - The shortest path and its cost

Time Complexity

O(b^d) where b is the branching factor and d is the depth of the solution. In the worst case with an inadmissible heuristic: O(V²). With a perfect heuristic: O(V). Typical case with good heuristic: O(V log V).

Space Complexity

O(V) for the open set, closed set, and path reconstruction.

Note

The heuristic function must be admissible (never overestimate the actual cost) and consistent (satisfy the triangle inequality) to guarantee finding the optimal path.