最小费用最大流算法解释

最小费用最大流算法是一种在网络流问题中求解最大流的算法，同时也考虑了每条边的费用，使得在满足最大流的前提下，费用最小。以下是最小费用最大流算法的实现代码：

function [maxFlow, minCost] = minCostMaxFlow(capacity, cost, source, sink)
% capacity: 网络流图中每条边的容量
% cost: 网络流图中每条边的费用
% source: 源点
% sink: 汇点
% maxFlow: 最大流量
% minCost: 最小费用

n = length(capacity);
flow = zeros(n); % 流量矩阵
costMatrix = cost; % 费用矩阵

while true
    % 使用 Dijkstra 算法寻找增广路径
    [dist, prev] = dijkstra(costMatrix, source);
    if prev(sink) == -1 % 如果不存在增广路径，则退出循环
        break;
    end
    
    % 计算增广路径上的最小容量
    minCapacity = inf;
    node = sink;
    while node ~= source
        prevNode = prev(node);
        minCapacity = min(minCapacity, capacity(prevNode, node) - flow(prevNode, node));
        node = prevNode;
    end
    
    % 更新流量矩阵和费用矩阵
    node = sink;
    while node ~= source
        prevNode = prev(node);
        flow(prevNode, node) = flow(prevNode, node) + minCapacity;
        flow(node, prevNode) = flow(node, prevNode) - minCapacity;
        costMatrix(prevNode, node) = cost(prevNode, node) - dist(sink) + dist(prevNode);
        costMatrix(node, prevNode) = cost(node, prevNode) + dist(sink) - dist(prevNode);
        node = prevNode;
    end
end

% 计算最大流量和最小费用
maxFlow = sum(flow(source, :));
minCost = sum(flow.*cost);

end

function [dist, prev] = dijkstra(costMatrix, source)
% 使用 Dijkstra 算法寻找增广路径
n = length(costMatrix);
dist = inf(1, n);
prev = -ones(1, n);
visited = false(1, n);

dist(source) = 0;

for i = 1:n
    % 找到未访问节点中距离最小的节点
    [~, u] = min(dist .* ~visited);
    if isinf(dist(u))
        break;
    end
    
    visited(u) = true;
    
    % 更新与 u 相邻的节点的距离
    for v = 1:n
        if ~visited(v) && costMatrix(u, v) < inf
            alt = dist(u) + costMatrix(u, v);
            if alt < dist(v)
                dist(v) = alt;
                prev(v) = u;
            end
        end
    end
end

end