matlab图论程序算法大全.pdf

精心整理2019 年 9 月图论算法matlab实现求最小费用最大流算法的求最小费用最大流算法的 MATLABMATLAB 程序代码如下：程序代码如下：n=5;C=0 15 16 0 00 0 0 13 140 11 0 17 00 0 0 0 80 0 0 0 0;%弧容量b=0 4 1 0 00 0 0 6 10 2 0 3 00 0 0 0 20 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;endfor(i=2:n)p(i)=Inf;s(i)=i;end%用Ford 算法求最短路,赋初值for(k=1:n)pd=1;%求有向赋权图中vs 到vt 的最短路精心整理2019 年 9 月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;endif(pd)break;end;end%求最短路的Ford 算法结束if(p(n)=Inf)break;end%不存在vs 到vt 的最短路,算法终止.注意在求最小费用最大流时构造有向赋权图中不会含负权回路,所以不会出现k=ndvt=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)dvtt)dvt=dvtt;endif(s(t)=1)break;end%当t 的标号为vs 时,终止计算调整量t=s(t);end%继续调整前一段弧上的流fpd=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)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;endk=k-1%显示A中所有不同正数的个数for(i=1:k-1)for(j=i+1:k)%将x 中不同的正数从小到大排序if(x(j)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;endif(pd)T(i,j)=0;T(j,i)=0;%假如TT 中有圈else q=q+1;end;end;end;end;endT%显示近似最小生成树T,程序结束用用Warshall-FloydWarshall-Floyd 算法求任意两点间的最短路算法求任意两点间的最短路.n=8;A=0 2 8 1 Inf Inf Inf Inf2 0 6 Inf 1 Inf Inf Inf8 6 0 7 5 1 2 Inf1 Inf 7 0 Inf Inf 9 InfInf 1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6精心整理2019 年 9 月Inf Inf 2 9 Inf 4 0 3Inf 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);%更新dijR(i,j)=k;end;end;end%更新rijk%显示迭代步数D%显示每步迭代后的路长R%显示每步迭代后的路径pd=0;for i=1:n%含有负权时if(D(i,i)0)pd=1;break;end;end%存在一条含有顶点vi 的负回路if(pd)break;end%存在一条负回路,终止程序end%程序结束利用利用 Ford-FulkersonFord-Fulkerson 标号法求最大流算法的标号法求最大流算法的MATLABMATLAB 程序代码如下：程序代码如下：n=8;C=0 5 4 3 0 0 0 00 0 0 0 5 3 0 00 0 0 0 0 3 2 00 0 0 0 0 0 2 00 0 0 0 0 0 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 5精心整理2019 年 9 月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-19while(1)No(1)=n+1;d(1)=Inf;%给发点vs 标号while(1)pd=1;%标号过程for(i=1:n)if(No(i)%选择一个已标号的点vifor(j=1:n)if(No(j)=0&f(i,j)d(i)d(j)=d(i);endelseif(No(j)=0&f(j,i)0)%对于未给标号的点vj,当vjvi 为非零流弧时No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)d(i)d(j)=d(i);end;end;end;end;endif(No(n)|pd)break;end;end%若收点vt 得到标号或者无法标号,终止标号过程if(pd)break;end%vt 未得到标号,f 已是最大流,算法终止dvt=d(n);t=n;%进入调整过程,dvt 表示调整量while(1)if(No(t)0)f(No(t),t)=f(No(t),t)+dvt;%前向弧调整elseif(No(t)0)f(No(t),t)=f(No(t),t)-dvt;end%后向弧调整if(No(t)=1)for(i=1:n)No(i)=0;d(i)=0;end;break;end%当t 的标号为vs 时,终止调整过程精心整理2019 年 9 月t=No(t);end;end;%继续调整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end%计算最大流量f%显示最大流wf%显示最大流量No%显示标号,由此可得最小割,程序结束图论程序大全图论程序大全程序一：关联矩阵和邻接矩阵互换算法程序一：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f)if f=0 m=sum(sum(F)/2;n=size(F,1);W=zeros(n,m);k=1;for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1;W(j,k)=1;k=k+1;end end endelseif f=1 m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:m a=find(F(:,i)=0);W(a(1),a(2)=1;W(a(2),a(1)=1;endelse fprint(Please imput the right value of f);endW;程序二：可达矩阵算法程序二：可达矩阵算法function P=dgraf(A)精心整理2019 年 9 月n=size(A,1);P=A;for i=2:n P=P+Ai;endP(P=0)=1;P;程序三：有向图关联矩阵和邻接矩阵互换算法程序三：有向图关联矩阵和邻接矩阵互换算法function W=mattransf(F,f)if f=0 m=sum(sum(F);n=size(F,1);W=zeros(n,m);k=1;for i=1:n for j=i:n if F(i,j)=0 W(i,k)=1;W(j,k)=-1;k=k+1;end end endelseif f=1 m=size(F,2);n=size(F,1);W=zeros(n,n);for i=1:m a=find(F(:,i)=0);if F(a(1),i)=1 W(a(1),a(2)=1;else W(a(2),a(1)=1;end end else fprint(Please imput the right value of f);endW;第二讲：最短路问题第二讲：最短路问题程序一：程序一：DijkstraDijkstra算法（计算两点间的最短路）算法（计算两点间的最短路）function l,z=Dijkstra(W)精心整理2019 年 9 月n=size(W,1);for i=1:n l(i)=W(1,i);z(i)=0;end i=1;while il(j)+W(j,i)l(i)=l(j)+W(j,i);z(i)=j-1;if ji i=j-1;end end end i=i+1;end程序二：程序二：floydfloyd 算法（计算任意两点间的最短距离算法（计算任意两点间的最短距离）function d,r=floyd(a)n=size(a,1);d=a;for i=1:n for j=1:n r(i,j)=j;end end r;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);r(i,j)=r(i,k);end end end end程序三：程序三：n2short.mn2short.m 计算指定两点间的最短距离计算指定两点间的最短距离function P u=n2short(W,k1,k2)n=length(W);U=W;m=1;精心整理2019 年 9 月while mU(i,m)+U(m,j)U(i,j)=U(i,m)+U(m,j);end end end m=m+1;endu=U(k1,k2);P1=zeros(1,n);k=1;P1(k)=k2;V=ones(1,n)*inf;kk=k2;while kk=k1 for i=1:n V(1,i)=U(k1,kk)-W(i,kk);if V(1,i)=U(k1,i)P1(k+1)=i;kk=i;k=k+1;end endendk=1;wrow=find(P1=0);for j=length(wrow):-1:1 P(k)=P1(wrow(j);k=k+1;endP;程序四、程序四、n1short.m(n1short.m(计算某点到其它所有点的最短距离计算某点到其它所有点的最短距离)functionPm D=n1short(W,k)n=size(W,1);D=zeros(1,n);for i=1:n P d=n2short(W,k,i);Pmi=P;D(i)=d;end程序五：程序五：pass2short.m(pass2short.m(计算经过某两点的最短距离计算经过某两点的最短距离)精心整理2019 年 9 月function P d=pass2short(W,k1,k2,t1,t2)p1 d1=n2short(W,k1,t1);p2 d2=n2short(W,t1,t2);p3 d3=n2short(W,t2,k2);dt1=d1+d2+d3;p4 d4=n2short(W,k1,t2);p5 d5=n2short(W,t2,t1);p6 d6=n2short(W,t1,k2);dt2=d4+d5+d6;if dt1dt2 d=dt1;P=p1 p2(2:length(p2)p3(2:length(p3);else d=dt1;p=p4 p5(2:length(p5)p6(2:length(p6);endP;d;第三讲：最小生成树第三讲：最小生成树程序一：最小生成树的程序一：最小生成树的KruskalKruskal算法算法function T c=krusf(d,flag)if nargin=1 n=size(d,2);m=sum(sum(d=0)/2;b=zeros(3,m);k=1;for i=1:n for j=(i+1):n if d(i,j)=0 b(1,k)=i;b(2,k)=j;b(3,k)=d(i,j);k=k+1;end end endelse b=d;end n=max(max(b(1:2,:);m=size(b,2);B,i=sortrows(b,3);B=B;c=0;T=;精心整理2019 年 9 月 k=1;t=1:n;for i=1:m if t(B(1,i)=t(B(2,i)T(1:2,k)=B(1:2,i);c=c+B(3,i);k=k+1;tmin=min(t(B(1,i),t(B(2,i);tmax=max(t(B(1,i),t(B(2,i);for j=1:n if t(j)=tmax t(j)=tmin;end end end if k=n break;end endT;c;程序二：最小生成树的程序二：最小生成树的PrimPrim算法算法function T c=Primf(a)l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;listV(1)=1;e=1;while(ea(i,j)min=a(i,j);b=a(i,j);s=i;d=j;end end end end listV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;精心整理2019 年 9 月 e=e+1;endT=source;destination;for g=1:e-1 c(g)=a(T(1,g),T(2,g);endc;另外两种程序另外两种程序最小生成树程序最小生成树程序1 1（primprim 算法构造最小生成树）算法构造最小生成树）a=inf 50 60 inf inf inf inf;50 inf inf 65 40 inf inf;60 inf inf 52 inf inf 45;.inf 65 52 inf 50 30 42;inf 40 inf 50 inf 70 inf;inf inf inf 30 70 inf inf;.inf inf 45 42 inf inf inf;result=;p=1;tb=2:length(a);while length(result)=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult 最小生成树程序最小生成树程序 2 2（KruskalKruskal 算法构造最小生成树）算法构造最小生成树）clc;clear;精心整理2019 年 9 月a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j,b=find(a);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;while length(result)looptemp=min(data(3,:);flag=find(data(3,:)=temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);if index(1,flag)=index(2,flag)result=result,data(:,flag);endindex(find(index=v2)=v1;data(:,flag)=;index(:,flag)=;endresult第四讲：第四讲：EulerEuler 图和图和 HamiltonHamilton 图图精心整理2019 年 9 月程序一：程序一：FleuryFleury 算法（在一个算法（在一个 EulerEuler 图中找出图中找出 EulerEuler 环游）环游）注：包括三个文件；fleuf1.m,edf.m,flecvexf.mfunction T c=fleuf1(d)%注：必须保证是Euler环游，否则输出T=0,c=0n=length(d);b=d;b(b=inf)=0;b(b=0)=1;m=0;a=sum(b);eds=sum(a)/2;ed=zeros(2,eds);vexs=zeros(1,eds+1);matr=b;for i=1:n if mod(a(i),2)=1 m=m+1;endendif m=0 fprintf(there is not exit Euler path.n)T=0;c=0;endif m=0 vet=1;flag=0;t1=find(matr(vet,:)=1);for ii=1:length(t1)ed(:,1)=vet,t1(ii);vexs(1,1)=vet;vexs(1,2)=t1(ii);matr(vexs(1,2),vexs(1,1)=0;flagg=1;tem=1;while flagg flagg ed=edf(matr,eds,vexs,ed,tem);tem=tem+1;if ed(1,eds)=0&ed(2,eds)=0 T=ed;T(2,eds)=1;c=0;for g=1:eds c=c+d(T(1,g),T(2,g);end精心整理2019 年 9 月 flagg=0;break;end end endendfunctionflag ed=edf(matr,eds,vexs,ed,tem)flag=1;for i=2:eds dvex f=flecvexf(matr,i,vexs,eds,ed,tem);if f=1 flag=0;break;end if dvex=0 ed(:,i)=vexs(1,i)dvex;vexs(1,i+1)=dvex;matr(vexs(1,i+1),vexs(1,i)=0;else break;endendfunction dvex f=flecvexf(matr,i,vexs,eds,ed,temp)f=0;edd=find(matr(vexs(1,i),:)=1);dvex=0;dvex1=;ded=;if length(edd)=1 dvex=edd;else dd=1;dd1=0;kkk=0;for kk=1:length(edd)m1=find(vexs=edd(kk);if sum(m1)=0 dvex1(dd)=edd(kk);dd=dd+1;dd1=1;else kkk=kkk+1;end end if kkk=length(edd)tem=vexs(1,i)*ones(1,kkk);edd1=tem;edd;精心整理2019 年 9 月 for l1=1:kkk lt=0;ddd=1;for l2=1:eds if edd1(1:2,l1)=ed(1:2,l2)lt=lt+1;end end if lt=0 ded(ddd)=edd(l1);ddd=ddd+1;end end end if templength(dvex1)&temp=length(ded)dvex=ded(temp);else f=1;endend程序二：程序二：HamiltonHamilton改良圈算法（找出比较好的改良圈算法（找出比较好的HamiltonHamilton路）路）function C d1=hamiltonglf(v)%d表示权值矩阵%C表示算法最终找到的Hamilton圈。%v=51 67;37 84;41 94;2 99;18 54;4 50;24 42;25 38;13 40;7 64;22 60;25 62;18 40;41 26;n=size(v,1);subplot(1,2,1)hold on;plot(v(:,1),v(:,2),*);%描点for i=1:n str1=V;str2=num2str(i);dot=str1,str2;text(v(i,1)-1,v(i,2)-2,dot);%给点命名endplot(v(:,1),v(:,2);%连线plot(v(n,1),v(1,1),v(n,2),v(1,2);for i=1:n for j=1:n d(i,j)=sqrt(v(i,1)-v(j,1)2+(v(i,2)-v(j,2)2);end精心整理2019 年 9 月endd2=0;for i=1:n if i3 for m=4:n+1 for i=1:(m-3)for j=(i+2):(m-1)if(d(C(i),C(j)+d(C(i+1),C(j+1)d(C(i),C(i+1)+d(C(j),C(j+1)C1(1:i)=C(1:i);for k=(i+1):j C1(k)=C(j+i+1-k);end C1(j+1):m)=C(j+1):m);end end end end elseif n=3 if nfloor(a(1)/n)t2=floor(a(1)/n)+1;else t2=floor(a(1)/n);end J(t1,t2)=1,J(t2,t1)=1;W(t1,:)=0;W(t2,:)=0;W(:,t1)=0;W(:,t2)=0;endJ;程序二：匈牙利算法（完美匹配算法程序二：匈牙利算法（完美匹配算法,包括三个文件包括三个文件fc01,fc02,fc03fc01,fc02,fc03）function e,s=fc01(a,flag)if nargin=1 flag=0;endb=a;if flag=0 cmax=max(max(b);b=cmax-b;endm=size(b);精心整理2019 年 9 月for i=1:m(1)b(i,:)=b(i,:)-min(b(i,:);endfor j=1:m(2)b(:,j)=b(:,j)-min(b(:,j);endd=(b=0);e,total=fc02(d);while total=m(1)b=fc03(b,e);d=(b=0);e,total=fc02(d);endinx=sub2ind(size(a),e(:,1),e(:,2);e=e,a(inx);s=sum(a(inx);function e,total=fc02(d)total=0;m=size(d);e=zeros(m(1),2);t=sum(sum(d);nump=sum(d);while t=0 s,inp=sort(nump);inq=find(s);ep=inp(inq(1);inp=find(d(ep,:);numq=sum(d(:,inp);s,inq=sort(numq);eq=inp(inq(1);total=total+1;e(total,:)=ep,eq;inp=find(d(:,eq);nump(inp)=nump(inp)-1;nump(ep)=0;t=t-sum(d(ep,:)-sum(d(:,eq)+1;d(ep,:)=0*d(ep,:);d(:,eq)=0*d(:,eq);endfunction b=fc03(b,e)m=size(b);t=1;p=ones(m(1),1);q=zeros(m(1),1);inp=find(e(:,1)=0);p(e(inp,1)=0;while t=0精心整理2019 年 9 月 tp=sum(p+q);inp=find(p=1);n=size(inp);for i=1:n(1)inq=find(b(inp(i),:)=0);q(inq)=1;end inp=find(q=1);n=size(inp);for i=1:n(1)if all(e(:,2)-inp(i)=0 inq=find(e(:,2)-inp(i)=0);p(e(inq)=1;end end tq=sum(p+q);t=tq-tp;endinp=find(p=1);inq=find(q=0);cmin=min(min(b(inp,inq);inq=find(q=1);b(inp,:)=b(inp,:)-cmin;b(:,inq)=b(:,inq)+cmin;运行以下程序求其最大解：输入矩阵a，然后输入t,m=fc01(a)运行以下程序求其最小解：输入矩阵a，然后输入t,m=fc01(a，1)匈牙利算法的另一程序匈牙利算法的另一程序匈牙利算法的 MATLAB 程序代码如下：m=5;n=5;A=0 1 1 0 01 1 0 1 10 1 1 0 00 1 1 0 00 0 0 1 1;M(m,n)=0;精心整理2019 年 9 月for(i=1:m)for(j=1:n)if(A(i,j)M(i,j)=1;break;end;end%求初始匹配Mif(M(i,j)break;end;end%获得仅含一条边的初始匹配Mwhile(1)for(i=1:m)x(i)=0;end%将记录X中点的标号和标记*for(i=1:n)y(i)=0;end%将记录Y中点的标号和标记*for(i=1:m)pd=1;%寻找X中M的所有非饱和点for(j=1:n)if(M(i,j)pd=0;end;endif(pd)x(i)=-n-1;end;end%将X中M的所有非饱和点都给以标号0 和标记*,程序中用n+1 表示0 标号,标号为负数时表示标记*pd=0;while(1)xi=0;for(i=1:m)if(x(i)1)k=k-1;for(j=1:k)pdd=1;for(i=1:m)if(M(i,yy(j)x(i)=-yy(j);pdd=0;break;end;end%将yj 在M中与之邻接的点xk(即xkyjM),给以标号j 和标记*if(pdd)break;end;endif(pdd)k=1;j=yy(j);%yj 不是M的饱和点while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j);%任取M的一个非饱和点yj,逆向返回if(j=n+1)break;end%找到X中标号为0 的点时结束,获得M-增广路Pk=k+1;endfor(i=1:k)if(M(P(i,1),P(i,2)M(P(i,1),P(i,2)=0;%将匹配M 在增广路P 中出现的边去掉else M(P(i,1),P(i,2)=1;end;end%将增广路P 中没有在匹配M中出现的边加入到匹配M中break;end;end;endif(pd)break;end;end%假如X中所有有标号的点都已去掉了标记*,算法终止精心整理2019 年 9 月M%显示最大匹配M,程序结束程序程序3 3 Kuhn-MunkresKuhn-Munkres算法（即赋权完备二元图的最佳匹配算法（即赋权完备二元图的最佳匹配程序）程序）function kk=kexingdian(A)%求赋权完备二元图最佳匹配A=4 5 5 1;2 2 4 6;4 2 3 3;5 0 2 1;%A 为邻接矩阵n=length(A);for(i=1:n)L(i,1)=0;L(i,2)=0;end for(i=1:n)for(j=1:n)if(L(i,1)L(S(i),1)+L(j,2)-A(S(i),j)al=L(S(i),1)+L(j,2)-A(S(i),j);end;end;end for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end%调整可行点标记 for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end%调整可行点标记 for(i=1:n)for(j=1:n)%生成子图 GL if(L(i,1)+L(j,2)=A(i,j)Gl(i,j)=1;else Gl(i,j)=0;end M(i,j)=0;k=0;end;end ii=0;jj=0;for(i=1:n)for(j=1:n)if(Gl(i,j)ii=i;jj=j;break;end;end if(ii)break;end;end%获得仅含 Gl 的一条边的初始匹配 M M(ii,jj)=1;break else%NL(S)T 精心整理2019 年 9 月 for(j=1:jsn)pd=1;%取 yNL(S)T for(k=1:jst)if(T(k)=NlS(j)pd=0;break;end;end if(pd)jj=j;break;end;end pd=0;%判断 y 是否为 M 的饱和点 for(i=1:n)if(M(i,NlS(jj)pd=1;ii=i;break;end;end if(pd)jss=jss+1;S(jss)=ii;jst=jst+1;T(jst)=NlS(jj);%S=Sx,T=Ty else%获得 Gl 的一条 M-增广路,调整匹配 M for(k=1:jst)M(S(k),T(k)=1;M(S(k+1),T(k)=0;end if(jst=0)k=0;end M(S(k+1),NlS(jj)=1;break;end;end;end;end MaxZjpp=0;for(i=1:n)for(j=1:n)if(M(i,j)MaxZjpp=MaxZjpp+A(i,j);end;end;end M%显示最佳匹配 M MaxZjpp%显示最佳匹配 M 的权,程序结束第六讲：最大流最小费用问题第六讲：最大流最小费用问题程序一：程序一：2F2F算法算法(Ford-Fulkerson(Ford-Fulkerson算法算法)，求最大流，求最大流%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 function f wf=fulkersonf(C,f1)%C表示容量%f1表示当前流量，默认为0%f表示最大流?%wf表示最大流的流量n=length(C);if nargin=1;f=zeros(n,n);else精心整理2019 年 9 月 f=f1;endNo=zeros(1,n);d=zeros(1,n);while(1)No(1)=n+1;d(1)=Inf;while(1)pd=1;for(i=1:n)if(No(i)for(j=1:n)if(No(j)=0&f(i,j)d(i)d(j)=d(i);end elseif(No(j)=0&f(j,i)0)No(j)=-i;d(j)=f(j,i);pd=0;if(d(j)d(i)d(j)=d(i);end end end end end if(No(n)|pd)break;end end if(pd)break;end dvt=d(n);t=n;while(1)if(No(t)0)f(No(t),t)=f(No(t),t)+dvt;elseif(No(t)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 for(k=1:n)pd=1;精心整理2019 年 9 月 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 if(p(n)=inf)break;end dvt=inf;t=n;while(1)if(a(s(t),t)0)dvtt=C(s(t),t)-f(s(t),t);elseif(a(s(t),t)dvtt)dvt=dvtt;end if(s(t)=1)break;end t=s(t);end 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=s(t);end精心整理2019 年 9 月 if(pd)break;end wf=0;for(j=1:n)wf=wf+f(1,j);endendzwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);endendf;图论工具箱：图论工具箱：基本图论函数库：基本图论函数库：DijkstraDijkstra 最短路径：最短路径：KruskalKruskal 最小生成树：最小生成树：PrimsPrims 算法：算法：A A 星优化算法：星优化算法：*