在网络流问题中，最大流只关心“最多能送多少货”，而现实场景往往还要考虑“送这些货花多少钱”。比如物流调度中，每条运输线路不仅有容量限制，还有单位运费，我们希望在运送指定数量货物的前提下让总运费最小，这就是最小费用流（Minimum Cost Flow）问题。本文将以Node.js为实现载体，用SSP（连续最短路）算法完整实现最小费用最大流，并深入剖析每个环节的原理。
最小费用流的核心思路：费用与流量的博弈
最小费用流问题的标准定义是：给定一个有向图，每条边有容量上限和单位流量费用，要求从源点s向汇点t运送指定流量（或最大流量），并且总费用尽可能小。这个问题可以拆解成两个子目标的叠加：既要满足流的可行性约束（容量限制、流量守恒），又要优化费用目标。
解决这类问题最直观的思路是贪心：每次都沿着费用最小的增广路推送流量，直到无法再增广或达到需求流量。这就是所谓的连续最短路算法（Successive Shortest Path，SSP）。它的正确性基于一个重要性质：每次沿最短（最便宜）路增广后，残余网络中仍然存在最短增广路，且总费用在每一步都是当前流量下的最小值。换句话说，如果把“流量-最小费用”看成一个函数，SSP保证每个中间流量值对应的费用都是最优的，所以算法天然支持“运送任意指定流量”的查询。
要实现SSP，有两个关键基础设施：一是残余网络，二是负权边最短路算法。残余网络中反向边的费用是原边费用的相反数，这导致图中不可避免地出现负权边，这一点直接影响了算法选型，下面详细展开。
为什么Dijkstra用不了？负权边与SPFA的选择
很多初学者在实现费用流时会直接套用Dijkstra算法，结果发现答案不对或者死循环。原因在于残余网络的构造方式：当一条费用为5的正向边被推送了流量后，会产生一条费用为-5的反向边，用于后续“反悔”。这条负权边破坏了Dijkstra的贪心前提——Dijkstra要求所有边权非负，否则已经确定最短距离的节点可能被更短路径再次更新。
处理负权边的经典选择有两个：Bellman-Ford和SPFA。Bellman-Ford的时间复杂度稳定在O(VE)，但每次增广都要跑一遍完整迭代，效率偏低。SPFA（Shortest Path Faster Algorithm）是Bellman-Ford的队列优化版本，平均表现远好于理论最坏复杂度O(VE)，在稀疏图上尤其高效。它的核心思想是用一个队列维护“距离可能被更新的节点”，只有被松弛成功的节点才会重新入队，避免了大量无效遍历。
还有一种工程上的折中方案：给每个节点加上势函数（Johnson算法的思路），把所有边权修正为非负后再用Dijkstra，配合优先队列可以实现更稳定的复杂度。不过对于大多数竞赛和实际场景，SPFA写法更简洁、易于调试，本文选择SPFA作为主实现。下面是SPFA寻找最短增广路的关键代码片段：
function spfa(graph, n, s, t) {
const dist = new Array(n).fill(Infinity);
const inQueue = new Array(n).fill(false);
const queue = [s];
dist[s] = 0;
inQueue[s] = true;
while (queue.length > 0) {
const u = queue.shift();
inQueue[u] = false;
for (const ei of graph.head[u]) {
const edge = graph.edges[ei];
if (edge.cap > 0 && dist[u] + edge.cost < dist[edge.to]) {
dist[edge.to] = dist[u] + edge.cost;
graph.preEdge[edge.to] = ei; // 记录前驱边，便于回溯增广路
if (!inQueue[edge.to]) {
queue.push(edge.to);
inQueue[edge.to] = true;
}
}
}
}
return dist[t] !== Infinity;
}Node.js完整实现：前向星存图与增广逻辑
存图采用链式前向星（边数组方式）：把正向边和反向边成对存储，第i条边与第i+1条边互为反向，通过按位异或运算ei ^ 1即可在O(1)时间内找到配对边。这种写法不需要额外的邻接矩阵，内存紧凑，配合Node.js的普通数组性能完全够用。
每轮循环先用SPFA判断汇点是否可达并求出最短费用路，然后沿前驱边回溯，找出这条路上残余容量最小的边作为本次推送流量，同时累加费用。正向边减容、反向边加容，重复直到找不到增广路，此时得到的流量就是最大流，累计费用就是最小费用。
class MinCostFlow {
constructor(n) {
this.n = n;
this.edges = []; // 边数组，成对存储
this.head = Array.from({ length: n }, () => []);
}
addEdge(from, to, cap, cost) {
this.edges.push({ to, cap, cost });
this.edges.push({ to: from, cap: 0, cost: -cost }); // 反向边费用取反
this.head[from].push(this.edges.length - 2);
this.head[to].push(this.edges.length - 1);
}
// 求最小费用最大流，返回 [最大流, 最小费用]
minCostMaxFlow(s, t) {
let flow = 0, cost = 0;
while (true) {
const dist = new Array(this.n).fill(Infinity);
const pre = new Array(this.n).fill(-1);
const inQueue = new Array(this.n).fill(false);
const queue = [s];
dist[s] = 0;
inQueue[s] = true;
while (queue.length > 0) {
const u = queue.shift();
inQueue[u] = false;
for (const ei of this.head[u]) {
const e = this.edges[ei];
if (e.cap > 0 && dist[u] + e.cost < dist[e.to]) {
dist[e.to] = dist[u] + e.cost;
pre[e.to] = ei;
if (!inQueue[e.to]) {
queue.push(e.to);
inQueue[e.to] = true;
}
}
}
}
if (dist[t] === Infinity) break; // 无增广路，算法结束
// 找增广路上的最小残余容量
let aug = Infinity;
for (let v = t; v !== s; ) {
const ei = pre[v];
aug = Math.min(aug, this.edges[ei].cap);
v = this.edges[ei ^ 1].to;
}
// 更新残余网络并累计费用
for (let v = t; v !== s; ) {
const ei = pre[v];
this.edges[ei].cap -= aug;
this.edges[ei ^ 1].cap += aug;
v = this.edges[ei ^ 1].to;
}
flow += aug;
cost += dist[t] * aug;
}
return [flow, cost];
}
}
// 使用示例：经典的运输网络
const mcmf = new MinCostFlow(4);
mcmf.addEdge(0, 1, 2, 1);
mcmf.addEdge(0, 2, 1, 3);
mcmf.addEdge(1, 2, 1, 1);
mcmf.addEdge(1, 3, 1, 4);
mcmf.addEdge(2, 3, 3, 1);
const [maxFlow, minCost] = mcmf.minCostMaxFlow(0, 3);
console.log('最大流：' + maxFlow + '，最小费用：' + minCost);
// 输出：最大流：3，最小费用：9代码中有几个细节值得注意。反向边的初始容量为0，费用为正向边的相反数，这样在回溯增广路时，通过ei ^ 1定位到反向边后，其to属性正好是路径上的前一个节点，用于迭代回溯非常方便。费用累计时直接用dist[t] * aug，因为dist[t]就是这条增广路上单位费用的总和，乘以推送量即为本次增广的费用增量。
进阶优化与替代方案对比
除了SSP，最小费用流还有其他求解思路，各有适用场景。消圈法（Cycle Canceling）先求任意一个可行流（比如用最大流算法），然后在残余网络中不断寻找负费用环并沿其推送流量来削减总费用，直到没有负环为止。消圈法实现简单直观，但每次找负环的开销不小，整体效率通常不如SSP，更多作为理论工具帮助理解对偶性。
网络单纯形法（Network Simplex）是工业级求解器的首选，它把线性规划单纯形法特化到网络结构上，在实际数据上速度极快，缺点是实现复杂度非常高，手工编写容易出错。如果只是需要解决问题而非学习算法，也可以考虑在Node.js中通过子进程调用外部求解器或使用JavaScript实现的线性规划库。
回到SSP本身的优化空间：一是用双端队列配合SLF（Small Label First）优化，让距离更小的节点优先出队，减少松弛次数；二是当图的边权非负或已做势函数修正时，换成Dijkstra加二叉堆，把单轮最短路的复杂度降为确定的O((V+E)logV)；三是数据规模较大时避免使用Array.prototype.shift操作队列，改用头指针下标模拟，减少数组元素搬移的开销。这些改进在节点数上万的大规模网络中收益明显。
最后提醒一个常见的坑：如果图中存在负费用环，SSP的前提会被破坏，此时问题可能无下界（费用可以无限减小）。建图时要确保初始网络中没有负环，或者先做特殊处理，否则增广过程可能陷入死循环。理解了这些边界条件，你就能在实际项目中放心地用这套Node.js实现处理调度、分配、运输等各类费用优化问题了。
Node.js最小费用流MinimumCostFlow修改时间：2026-09-09 16:27:59