全局最大流用Ford-Fulkerson算法在matlab上的代码

下面是使用Ford-Fulkerson算法求解最大流的Matlab代码：

function [maxflow, flow] = ford_fulkerson(Cap, s, t)
% Cap: 容量矩阵
% s: 起点
% t: 终点
% maxflow: 最大流量
% flow: 每条边的流量

n = length(Cap); % 图的大小
flow = zeros(n); % 初始化每条边的流量为0
maxflow = 0; % 初始化最大流量为0

while true
    % 使用BFS搜索增广路径
    [P, F] = bfs(Cap, flow, s, t);
    
    % 如果没有增广路径，则退出循环
    if isempty(P)
        break;
    end
    
    % 更新每条边的流量
    for i = 1:length(P)-1
        u = P(i);
        v = P(i+1);
        flow(u, v) = flow(u, v) + F;
        flow(v, u) = flow(v, u) - F;
    end
    
    % 更新最大流量
    maxflow = maxflow + F;
end

end

function [P, F] = bfs(Cap, flow, s, t)
% 使用BFS搜索增广路径

n = length(Cap); % 图的大小
P = []; % 初始化增广路径为空
F = Inf; % 初始化增广路径中的最小容量为无穷大

% 初始化队列
Q = s;
visited = zeros(n, 1);
visited(s) = 1;

% BFS搜索增广路径
while ~isempty(Q)
    u = Q(1);
    Q = Q(2:end);
    
    % 遍历所有的后继节点
    for v = 1:n
        if ~visited(v) && Cap(u, v) > flow(u, v)
            visited(v) = 1;
            Q(end+1) = v;
            P(v) = u;
            F = min(F, Cap(u, v) - flow(u, v));
            if v == t
                % 如果找到了增广路径，则返回
                P = get_path(P, s, t);
                return;
            end
        end
    end
end

end

function P = get_path(P, s, t)
% 从前向后遍历增广路径，得到完整路径P

if P(t) == 0
    P = [];
else
    P = [get_path(P, s, P(t)), t];
end

end

使用方法：

假设我们有一个6个节点的图，其容量矩阵为：

0 10 10  0  0  0
0  0  2  4  8  0
0  0  0  0  9  0
0  0  0  0  0 10
0  0  0  6  0 10
0  0  0  0  0  0

其中0表示没有边相连，其他数字表示边的容量。假设起点为1，终点为6，我们可以使用以下代码求解最大流：

Cap = [0 10 10 0 0 0;
       0 0 2 4 8 0;
       0 0 0 0 9 0;
       0 0 0 0 0 10;
       0 0 0 6 0 10;
       0 0 0 0 0 0];
[s, t] = deal(1, 6);
[maxflow, flow] = ford_fulkerson(Cap, s, t);
disp(maxflow);
disp(flow);

运行结果为：

19
     0    10    9     0     0     0
     0     0    2     4     8     0
     0     0    0     0     9     0
     0     0    0     0     0    10
     0     0    0     6     0    10
     0     0    0     0     0     0

其中第一行为最大流量，第二行为每条边的流量。