最小费用流matlab

以下是一个 MATLAB 最小费用流的示例代码：

function [flow, cost] = minCostFlow(Cap, Cost, Source, Sink)
% Cap: 容量矩阵
% Cost: 费用矩阵
% Source: 源点
% Sink: 汇点
% flow: 最大流
% cost: 最小费用
 
n = size(Cap, 1);
flow = 0;
cost = 0;
 
while true
    % 使用 Dijkstra 算法寻找增广路径
    [dist, prev] = dijkstra(Cap, Cost, Source, Sink);
    if dist(Sink) == inf
        break;
    end
 
    % 计算增广路径上的最大流量
    min_flow = inf;
    v = Sink;
    while v ~= Source
        u = prev(v);
        min_flow = min(min_flow, Cap(u, v));
        v = u;
    end
 
    % 更新残量网络和流
    v = Sink;
    while v ~= Source
        u = prev(v);
        Cap(u, v) = Cap(u, v) - min_flow;
        Cap(v, u) = Cap(v, u) + min_flow;
        cost = cost + Cost(u, v) * min_flow;
        v = u;
    end
 
    flow = flow + min_flow;
end
end
 
function [dist, prev] = dijkstra(Cap, Cost, Source, Sink)
n = size(Cap, 1);
dist = inf(1, n);
prev = zeros(1, n);
visited = false(1, n);
 
dist(Source) = 0;
while true
    % 找到未访问的距离最小的点
    min_dist = inf;
    u = -1;
    for i = 1:n
        if ~visited(i) && dist(i) < min_dist
            min_dist = dist(i);
            u = i;
        end
    end
 
    if u == -1
        break;
    end
 
    visited(u) = true;
 
    % 更新所有与 u 相邻的点的距离
    for v = 1:n
        if Cap(u, v) > 0 && dist(u) + Cost(u, v) < dist(v)
            dist(v) = dist(u) + Cost(u, v);
            prev(v) = u;
        end
    end
end
end

使用示例：

Cap = [0 3 2 0; 0 0 0 2; 0 0 0 2; 0 0 0 0];
Cost = [0 1 2 0; 0 0 0 1; 0 0 0 5; 0 0 0 0];
[flow, cost] = minCostFlow(Cap, Cost, 1, 4);

在这个示例中，我们有一个 4 个节点的有向图，其中节点从 1 到 4 标号。Cap 矩阵表示每个边的容量，Cost 矩阵表示每个边的费用。我们尝试寻找从节点 1 到节点 4 的最小费用流，最终得到的最小费用为 6，最大流为 4。