图论算法matlab实现
求最小费用最大流算法的 MATLAB 程序代码如下：
n=5;C=[0 15 16 0 0
0 0 0 13 14
0 11 0 17 0
0 0 0 0 8
0 0 0 0 0]; %弧容量
b=[0 4 1 0 0
0 0 0 6 1
0 2 0 3 0
0 0 0 0 2
0 0 0 0 0]; %弧上单位流量的费用
wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值
for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流
while(1)
for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图
for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end
for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值
for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路
for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end
if(pd)break;end;end %求最短路的Ford 算法结束
if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有
向赋权图中不会含负权回路, 所以不会出现k=n
dvt=Inf;t=n; %进入调整过程, dvt 表示调整量
while(1) %计算调整量
if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量
elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量
if(dvt>dvtt)dvt=dvtt;end
if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量
t=s(t);end %继续调整前一段弧上的流f
pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值
t=n;while(1) %调整过程
if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整
elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整
if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程
t=s(t);end
if(pd)break;end%如果最大流量达到预定的流量值
wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量
zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用
f %显示最小费用最大流
图 6-22
wf %显示最小费用最大流量
zwf %显示最小费用, 程序结束__
Kruskal 避圈法：
Kruskal 避圈法的MATLAB 程序代码如下：
n=8;A=[0 2 8 1 0 0 0 0
2 0 6 0 1 0 0 0
8 6 0 7 5 1 2 0
1 0 7 0 0 0 9 0
0 1 5 0 0 3 0 8
0 0 1 0 3 0 4 6
0 0 2 9 0 4 0 3
0 0 0 0 8 6 3 0];
k=1; %记录A中不同正数的个数
for(i=1:n-1)for(j=i+1:n) %此循环是查A中所有不同的正数
if(A(i,j)>0)x(k)=A(i,j); %数组x 记录A中不同的正数
kk=1; %临时变量
for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end %排除相同的正数
k=k+kk;end;end;end
k=k-1 %显示A中所有不同正数的个数
for(i=1:k-1)for(j=i+1:k) %将x 中不同的正数从小到大排序
if(x(j)<x(i))xx=x(j);x(j)=x(i);x(i)=xx;end;end;end
T(n,n)=0; %将矩阵T 中所有的元素赋值为0
q=0; %记录加入到树T 中的边数
for(s=1:k)if(q==n)break;end %获得最小生成树T, 算法终止
for(i=1:n-1)for(j=i+1:n)if (A(i,j)==x(s))T(i,j)=x(s);T(j,i)=x(s); %加入边到树T 中
TT=T; %临时记录T
while(1)pd=1; %砍掉TT 中所有的树枝
for(y=1:n)kk=0;
for(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;end %寻TT 中的树枝
if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end %砍掉TT 中的树枝
if(pd)break;end;end %已砍掉了TT 中所有的树枝
pd=0; %判断TT 中是否有圈
for(y=1:n-1)for(z=y+1:n)if(TT(y,z)>0)pd=1;break;end;end;end
if(pd)T(i,j)=0;T(j,i)=0; %假如TT 中有圈
else q=q+1;end;end;end;end;end
T %显示近似最小生成树T, 程序结束
用Warshall-Floyd 算法求任意两点间的最短路.
n=8;A=[0 2 8 1 Inf Inf Inf Inf
2 0 6 Inf 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 Inf 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞
D=A; %赋初值
for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值
for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,j); %更新dij
R(i,j)=k;end;end;end %更新rij
k %显示迭代步数
D %显示每步迭代后的路长
R %显示每步迭代后的路径
pd=0;for i=1:n %含有负权时
if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点vi 的负回路
matlab中fprintf是什么意思if(pd)break;end %存在一条负回路, 终止程序
end %程序结束
利用 Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码如下：
n=8;C=[0 5 4 3 0 0 0 0
0 0 0 0 5 3 0 0
0 0 0 0 0 3 2 0
0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0]; %弧容量
for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流
for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号
图 6-19
while(1)
No(1)=n+1;d(1)=Inf; %给发点vs 标号
while(1)pd=1; %标号过程

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。