Maximum and minimum cost assignments using the Hungarian/Munkres algorithm for n × m cost matrices.
deno add jsr:@alg/munkres
Other Install Options
npx jsr add @alg/munkresbunx jsr add @alg/munkrespnpm i jsr:@alg/munkresyarn add jsr:@alg/munkresvlt install jsr:@alg/munkres@alg/munkres provides min/max cost functions and min/max assignment functions.
The cost functions return the cost of a maximum or minimum assignment:
import {minCost, maxCost} from "@alg/munkres";
const costMatrix = [
[8, 4, 7],
[5, 2, 3],
[9, 4, 8],
];
console.log(minCost(costMatrix)); // 15
console.log(maxCost(costMatrix)); // 18The assignment functions return the indices in the cost matrix for a minimum or maximum assignment:
import {minAssignment, maxAssignment} from "@alg/munkres";
const costMatrix = [
[8, 4, 7],
[5, 2, 3],
[9, 4, 8],
];
console.log(minAssignment(costMatrix)); // [ [ 0, 0 ], [ 1, 2 ], [ 2, 1 ] ]
console.log(maxAssignment(costMatrix)); // [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ] ]All cost and assignment functions handle any n × m matrices:
import {minAssignment, maxAssignment} from "@alg/munkres";
const wide = [
[4, 5, 8, 7],
[2, 12, 6, 5],
[7, 8, 3, 9],
];
const long = [
[11, 13, 13],
[7, 21, 13],
[10, 7, 15],
[17, 11, 13],
[10, 13, 14],
];
console.log(minAssignment(wide)); // [ [ 0, 1 ], [ 1, 0 ], [ 2, 2 ] ]
console.log(maxAssignment(long)); // [ [ 1, 1 ], [ 2, 2 ], [ 3, 0 ] ]