# Function bevy::utils::petgraph::algo::astar::astar

``````pub fn astar<G, F, H, K, IsGoal>(
graph: G,
start: <G as GraphBase>::NodeId,
is_goal: IsGoal,
edge_cost: F,
estimate_cost: H
) -> Option<(K, Vec<<G as GraphBase>::NodeId, Global>)>where
G: IntoEdges + Visitable,
IsGoal: FnMut(<G as GraphBase>::NodeId) -> bool,
<G as GraphBase>::NodeId: Eq + Hash,
F: FnMut(<G as IntoEdgeReferences>::EdgeRef) -> K,
H: FnMut(<G as GraphBase>::NodeId) -> K,
K: Measure + Copy,``````
Expand description

[Generic] A* shortest path algorithm.

Computes the shortest path from `start` to `finish`, including the total path cost.

`finish` is implicitly given via the `is_goal` callback, which should return `true` if the given node is the finish node.

The function `edge_cost` should return the cost for a particular edge. Edge costs must be non-negative.

The function `estimate_cost` should return the estimated cost to the finish for a particular node. For the algorithm to find the actual shortest path, it should be admissible, meaning that it should never overestimate the actual cost to get to the nearest goal node. Estimate costs must also be non-negative.

The graph should be `Visitable` and implement `IntoEdges`.

## Example

``````use petgraph::Graph;
use petgraph::algo::astar;

let mut g = Graph::new();
let a = g.add_node((0., 0.));
let b = g.add_node((2., 0.));
let c = g.add_node((1., 1.));
let d = g.add_node((0., 2.));
let e = g.add_node((3., 3.));
let f = g.add_node((4., 2.));
g.extend_with_edges(&[
(a, b, 2),
(a, d, 4),
(b, c, 1),
(b, f, 7),
(c, e, 5),
(e, f, 1),
(d, e, 1),
]);

// Graph represented with the weight of each edge
// Edges with '*' are part of the optimal path.
//
//     2       1
// a ----- b ----- c
// | 4*    | 7     |
// d       f       | 5
// | 1*    | 1*    |
// \------ e ------/

let path = astar(&g, a, |finish| finish == f, |e| *e.weight(), |_| 0);
assert_eq!(path, Some((6, vec![a, d, e, f])));``````

Returns the total cost + the path of subsequent `NodeId` from start to finish, if one was found.