Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const compare = (a, b) => a[0] - b[0];
- const amount_to_node = amount => [amount];
- /* Single commodity, maximum flow, minimum cost optimizer, msand@seaber.io */
- function optimize(supplies, demands, costs) {
- const supply_nodes = supplies.map(amount_to_node);
- const demand_nodes = demands.map(amount_to_node);
- const num_supplies = supplies.length;
- const num_demands = demands.length;
- const edges = [];
- for (let from = 0; from < num_supplies; from++) {
- const f = costs[from];
- const supply = supply_nodes[from];
- for (let to = 0; to < num_demands; to++) {
- const demand = demand_nodes[to];
- const cost = f[to];
- edges.push([
- cost,
- supply,
- demand,
- from,
- to,
- ]);
- }
- }
- edges.sort(compare); // Most expensive part of the function
- const num_edges = edges.length; // = num_supplies * num_demands;
- for (let e = 0; e < num_edges; e++) {
- const edge = edges[e];
- const supply = edge[1];
- const demand = edge[2];
- const amount = Math.min(supply[0], demand[0]);
- supply[0] -= amount;
- demand[0] -= amount;
- edge[5] = amount;
- }
- return edges;
- }
- const supplies = [12, 23];
- const demands = [7, 17];
- const costs = [[3, 6], [5, 7]];
- console.log(optimize(supplies, demands, costs));
- ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement