Function pathfinding::directed::yen::yen

pub fn yen<N, C, FN, IN, FS>(
    start: &N,
    successors: FN,
    success: FS,
    k: usize
) -> Vec<(Vec<N>, C)>
where
    N: Eq + Hash + Clone,
    C: Zero + Ord + Copy,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = (N, C)>,
    FS: FnMut(&N) -> bool,

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());