# Function bevy::utils::petgraph::algo::k_shortest_path::k_shortest_path

``````pub fn k_shortest_path<G, F, K>(
graph: G,
start: <G as GraphBase>::NodeId,
goal: Option<<G as GraphBase>::NodeId>,
k: usize,
edge_cost: F
) -> HashMap<<G as GraphBase>::NodeId, K, RandomState>where
G: IntoEdges + Visitable + NodeCount + NodeIndexable,
<G as GraphBase>::NodeId: Eq + Hash,
F: FnMut(<G as IntoEdgeReferences>::EdgeRef) -> K,
K: Measure + Copy,``````
Expand description

[Generic] k’th shortest path algorithm.

Compute the length of the k’th shortest path from `start` to every reachable node.

The graph should be `Visitable` and implement `IntoEdges`. The function `edge_cost` should return the cost for a particular edge, which is used to compute path costs. Edge costs must be non-negative.

If `goal` is not `None`, then the algorithm terminates once the `goal` node’s cost is calculated.

Computes in *O(k * (|E| + |V|log(|V|))) time (average).

Returns a `HashMap` that maps `NodeId` to path cost.

## Example

``````use petgraph::Graph;
use petgraph::algo::k_shortest_path;
use petgraph::prelude::*;
use std::collections::HashMap;

let mut graph : Graph<(),(),Directed>= Graph::new();
let a = graph.add_node(()); // node with no weight
// z will be in another connected component

graph.extend_with_edges(&[
(a, b),
(b, c),
(c, d),
(d, a),
(e, f),
(b, e),
(f, g),
(g, h),
(h, e)
]);
// a ----> b ----> e ----> f
// ^       |       ^       |
// |       v       |       v
// d <---- c       h <---- g

let expected_res: HashMap<NodeIndex, usize> = [
(a, 7),
(b, 4),
(c, 5),
(d, 6),
(e, 5),
(f, 6),
(g, 7),
(h, 8)
].iter().cloned().collect();
let res = k_shortest_path(&graph,b,None,2, |_| 1);
assert_eq!(res, expected_res);
// z is not inside res because there is not path from b to z.``````