Function pathfinding::kuhn_munkres::kuhn_munkres_min

pub fn kuhn_munkres_min<C, W>(weights: &W) -> (C, Vec<usize>)
where
    C: Bounded + Sum<C> + Zero + Signed + Ord + Copy,
    W: Weights<C>,

Compute a minimum weight maximum matching between two disjoints sets of vertices using the Kuhn-Munkres algorithm (also known as Hungarian algorithm).

The weights between the first and second sets are given into the weights adjacency matrix. The return value is a pair with the total assignments weight, and a vector containing the column corresponding the every row.

For this reason, the number of rows must not be larger than the number of columns as no row will be left unassigned.

This algorithm executes in O(n³) where n is the cardinality of the sets.

See also

To maximize the sum of weights instead of minimizing it, use the kuhn_munkres() function.

Panics

This function panics if the number of rows is larger than the number of columns, or if the total assignments weight overflows or underflows.

Also, using indefinite values such as positive or negative infinity or NaN can cause this function to loop endlessly.