Function pathfinding::astar_bag [−] [src]

pub fn astar_bag<N, C, FN, IN, FH, FS>(
    start: &N, 
    neighbours: FN, 
    heuristic: FH, 
    success: FS
) -> (Vec<Vec<N>>, C) where
    N: Eq + Hash + Clone,
    C: Zero + Ord + Copy,
    FN: Fn(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FH: Fn(&N) -> C,
    FS: Fn(&N) -> bool, 

Compute all shortest paths using the A* search algorithm. Whereas astar (non-deterministically) returns a single shortest path, astar_bag returns all shortest paths (in a non-deterministic order).

The shortest paths starting from start up to a node for which success returns true are computed and returned in a Vec along with the cost (which, by definition, is the same for each shortest path). If no paths are found, the vector will be empty.

  • start is the starting node.
  • neighbours returns a list of neighbours for a given node, along with the cost for moving from the node to the neighbour.
  • heuristic returns an approximation of the cost from a given node to the goal. The approximation must not be greater than the real cost, or a wrong shortest path may be returned.
  • success checks whether the goal has been reached. It is not a node as some problems require a dynamic solution instead of a fixed node.

A node will never be included twice in the path as determined by the Eq relationship.

Each path comprises both the start and an end node. Note that while every path shares the same start node, different paths may have different end nodes.

Warning

The number of results with the same value might be very large in some graphs. Use with caution.