资源简介
无向图中的最大流算法MATLAB代码。注意:最后的hop calculation请忽略,与最大流算法无关。
代码片段和文件信息
function [hopmaxflowflowmatrix]=Maxflow_undirected(Cnsrcdes)
% source node: src
% destination node: des
% node number: n
% capacity matrix: C
% n=8;
% C= [0 5 4 3 0 0 0 0
% 5 0 0 0 5 3 0 0
% 4 0 0 0 0 3 2 0
% 3 0 0 0 0 0 2 0
% 0 5 0 0 0 0 0 4
% 0 3 3 0 0 0 0 3
% 0 0 2 2 0 0 0 5
% 0 0 0 0 4 3 5 0];
% src=1;des=5;
flowmatrix = zeros(nn);
%Nod 记录标号
No = zeros(1n);
d = zeros(1n);
while (1)
No(src) = n+1;
d(src) = Inf; %给发点vs 标号
while(1)
pd = 1; %标号过程
for i = 1:n
if (No(i)) %选择一个已标号的点vi
for j = 1:n
if (No(j) == 0 && flowmatrix(ij) < C(ij)) %对于未给标号的点vj 当vivj 为非饱和弧时
No(j) = i;
d(j) = C(ij) - flowmatrix(ij);
pd = 0;
if (d(j) > d(i))
d(j) = d(i);
end
elseif (No(j) == 0 && flowmatrix(ji) > 0) %对于未给标号的点vj 当vjvi 为非零流弧时
No(j) = -i;
评论
共有 条评论