Function pathfinding::directed::yen::yen
source · pub fn yen<N, C, FN, IN, FS>(
start: &N,
successors: FN,
success: FS,
k: usize,
) -> Vec<(Vec<N>, C)>
Expand description
Compute the k-shortest paths using the Yen’s search algorithm.
The k
-shortest paths starting from start
up to a node for which success
returns true
are computed along with their total cost. The result is return as a vector of (path, cost).
start
is the starting node.successors
returns a list of successors for a given node, along with the cost of moving from the node to the successor. Costs MUST be positive.success
checks weather the goal has been reached.k
is the amount of paths requests, including the shortest one.
The returned paths include both the start and the end node and are ordered by their costs starting with the lowest cost. If there exist less paths than requested, only the existing ones (if any) are returned.
§Example
We will search the 3 shortest paths from node C to node H. See https://en.wikipedia.org/wiki/Yen's_algorithm#Example for a visualization.
use pathfinding::prelude::yen;
// Find 3 shortest paths from 'c' to 'h'
let paths = yen(
&'c',
|c| match c {
'c' => vec![('d', 3), ('e', 2)],
'd' => vec![('f', 4)],
'e' => vec![('d', 1), ('f', 2), ('g', 3)],
'f' => vec![('g', 2), ('h', 1)],
'g' => vec![('h', 2)],
'h' => vec![],
_ => panic!(""),
},
|c| *c == 'h',
3);
assert_eq!(paths.len(), 3);
assert_eq!(paths[0], (vec!['c', 'e', 'f', 'h'], 5));
assert_eq!(paths[1], (vec!['c', 'e', 'g', 'h'], 7));
assert_eq!(paths[2], (vec!['c', 'd', 'f', 'h'], 8));
// An example of a graph that has no path from 'c' to 'h'.
let empty = yen(
&'c',
|c| match c {
'c' => vec![('d', 3)],
'd' => vec![],
_ => panic!(""),
},
|c| *c == 'h',
2);
assert!(empty.is_empty());