超全圖論matlab程序

1、 超全的圖論程序程序一：可達(dá)矩陣算法function P=dgraf(A)n=size(A,1);P=A;for i=2:n P=P+Ai;endP(P=0)=1; P;程序二：關(guān)聯(lián)矩陣和鄰接矩陣互換算法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

2、); 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;程序三：有向圖關(guān)聯(lián)矩陣和鄰接矩陣互換算法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=si

3、ze(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;第二講：最短路問題程序一：Dijkstra算法（計(jì)算兩點(diǎn)間的最短路）function l,z=Dijkstra(W)n = size (W,1);for i = 1 :n l(i)=W(1,i); z(i)=0;end i=1;while il(j)+

4、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程序二：floyd算法（計(jì)算任意兩點(diǎn)間的最短距離）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.m 計(jì)算指定兩點(diǎn)

5、間的最短距離function P u=n2short(W,k1,k2)n=length(W);U=W;m=1;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);fo

6、r j=length(wrow):-1:1 P(k)=P1(wrow(j); k=k+1;endP;程序四、n1short.m(計(jì)算某點(diǎn)到其它所有點(diǎn)的最短距離)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(計(jì)算經(jīng)過某兩點(diǎn)的最短距離)function P d=pass2short(W,k1,k2,t1,t2) p1 d1=n2short(W,k1,t1);p2 d2=n2short(W,t1,t2);p3 d3=n2

7、short(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;第三講：最小生成樹程序一：最小生成樹的Kruskal算法function T c=krusf(d,flag)if nargin=1 n=size(d,2); m

8、=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=; 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),

9、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;程序二：最小生成樹的Prim算法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)=

10、s; destination(e)=d; e=e+1;endT=source;destination;for g=1:e-1 c(g)=a(T(1,g),T(2,g);endc;另外兩種程序 最小生成樹程序1（prim 算法構(gòu)造最小生成樹）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 in

11、f;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（Kruskal 算法構(gòu)造最小生成樹）clc;clear;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)

12、=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)

13、=v1;data(:,flag)=;index(:,flag)=;endresult第四講：Euler圖和Hamilton圖程序一：Fleury算法（在一個(gè)Euler圖中找出Euler環(huán)游）注：包括三個(gè)文件；fleuf1.m, edf.m, flecvexf.mfunction T c=fleuf1(d)%注：必須保證是Euler環(huán)游，否則輸出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 mo

14、d(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+

15、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 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;

16、 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=

17、kkk+1; end end if kkk=length(edd) tem=vexs(1,i)*ones(1,kkk); edd1=tem;edd; 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程序二：Hamilton改良圈算法（找出比較

18、好的Hamilton路）function C d1= hamiltonglf(v)%d表示權(quán)值矩陣%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),*); %描點(diǎn)for i=1:n str1=V;str2=num2str(i); dot=str1,str2; text(v(i,1)-1,v(i,2)-2,dot); %給點(diǎn)命名

19、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); endendd2=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

20、); 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;程序二：匈牙利算法（完美匹配算法,包括三個(gè)文件fc01,fc02,fc03）function e,s=fc01(a,flag)if nargin=1 flag=0;endb=a;if flag=0 cmax=max(ma

21、x(b); b=cmax-b;endm=size(b);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

22、(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(:,

23、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 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

24、(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;運(yùn)行以下程序求其最大解：輸入矩陣a，然后輸入t,m=fc01(a) 運(yùn)行以下程序求其最小解：輸入矩陣a，然后輸入t,m=fc01(a，1)匈牙利算法的另一程序匈牙利算法的 MATLAB 程序代碼如下：m=5;n=5;A=0 1 1 0 01 1 0 1 10 1 1 0

25、00 1 1 0 00 0 0 1 1;M(m,n)=0;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中點(diǎn)的標(biāo)號和標(biāo)記*for(i=1:n)y(i)=0;end %將記錄Y中點(diǎn)的標(biāo)號和標(biāo)記*for(i=1:m)pd=1; %尋找X中M的所有非飽和點(diǎn)for(j=1:n)if(M(i,j)pd=0;end;endif(pd)x(i)=-n-1;end;end %將X中M的所有非飽和點(diǎn)都

26、給以標(biāo)號0 和標(biāo)記*, 程序中用n+1 表示0 標(biāo)號, 標(biāo)號為負(fù)數(shù)時(shí)表示標(biāo)記*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中與之鄰接的點(diǎn)xk (即xkyjM), 給以標(biāo)號j 和標(biāo)記*if(pdd)break;end;endif(pdd)k=1;j=yy(j); %yj 不是M的飽和點(diǎn)while(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j); %任取M的一個(gè)非飽和點(diǎn)yj, 逆向

27、返回if(j=n+1)break;end %找到X中標(biāo)號為0 的點(diǎn)時(shí)結(jié)束, 獲得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 中出現(xiàn)的邊去掉else M(P(i,1),P(i,2)=1;end;end %將增廣路P 中沒有在匹配M中出現(xiàn)的邊加入到匹配M中break;end;end;endif(pd)break;end;end %假如X中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*, 算法終止M %顯示最大匹配M, 程序結(jié)束程序3 Kuhn-Munkres算法（即賦權(quán)完備二元圖的最佳匹配程序）function

28、 kk=kexingdian(A)%求賦權(quán)完備二元圖最佳匹配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 %調(diào)整可行點(diǎn)標(biāo)記 for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end

29、%調(diào)整可行點(diǎn)標(biāo)記 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 for(j=1:jsn)pd=1; %取yNL(S)T for(k=1:jst)if(T(k)=NlS(j)

30、pd=0;break;end;end if(pd)jj=j;break;end;end pd=0; %判斷y是否為 M的飽和點(diǎn) 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-增廣路, 調(diào)整匹配 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;

31、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的權(quán), 程序結(jié)束第六講：最大流最小費(fèi)用問題程序一：2F算法(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 functi

32、on f wf=fulkersonf(C,f1)%C表示容量%f1表示當(dāng)前流量，默認(rèn)為0%f表示最大流%wf表示最大流的流量n=length(C);if nargin=1; f=zeros(n,n);else 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

33、)=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

34、(i,j); end end end for (i=2:n) p(i)=inf;s(i)=i; end for (k=1:n) pd=1; 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

35、; 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 if (pd) break; end wf=0; for (j=1:n) wf=wf+f(1,j); endendzwf=0;for (i=1:n) fo

36、r (j=1:n) zwf=zwf+b(i,j)*f(i,j); endendf;圖論工具箱： HYPERLINK /thread-295-1-1.html t _blank /thread-295-1-1.html基本圖論函數(shù)庫： HYPERLINK /thread-299-1-1.html t _blank /thread-299-1-1.htmlDijkstra最短路徑： HYPERLINK /thread-297-1-1.html t _blank /thread-297-1-1.htmlKruskal最小生成樹： HYPERLINK /thread-296-1-1.html t _b

37、lank /thread-296-1-1.htmlPrims算法： HYPERLINK /thread-300-1-1.html t _blank /thread-300-1-1.htmlA星優(yōu)化算法： HYPERLINK /thread-298-1-1.html t _blank /thread-298-1-1.html圖論算法及matlab實(shí)現(xiàn)用Warshall-Floyd 算法求任意兩點(diǎn)間的最短路.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

38、1 5 Inf 0 3 Inf 8Inf Inf 1 Inf 3 0 4 6Inf 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 %顯示迭代步數(shù)D %顯示每步迭代后的路長R %顯示每步迭代后的路徑pd=0

39、;for i=1:n %含有負(fù)權(quán)時(shí)if(D(i,i)0)x(k)=A(i,j); %數(shù)組x 記錄A中不同的正數(shù)kk=1; %臨時(shí)變量for(s=1:k-1)if(x(k)=x(s)kk=0;break;end;end %排除相同的正數(shù)k=k+kk;end;end;endk=k-1 %顯示A中所有不同正數(shù)的個(gè)數(shù)for(i=1:k-1)for(j=i+1:k) %將x 中不同的正數(shù)從小到大排序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

40、;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, 程序結(jié)束利用 Ford-Fulkerson 標(biāo)號法求最大流算法的MATLAB 程序代碼如下：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

41、 0 40 0 0 0 0 0 0 30 0 0 0 0 0 0 50 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 記錄標(biāo)號圖 6-19while(1)No(1)=n+1;d(1)=Inf; %給發(fā)點(diǎn)vs 標(biāo)號while(1)pd=1; %標(biāo)號過程for(i=1:n)if(No(i) %選擇一個(gè)已標(biāo)號的點(diǎn)vifor(j=1:n)if(No(j)=0&f(i,j)d(i)d(j)=d(i);endelseif(No(j)=0&f(j,i

42、)0) %對于未給標(biāo)號的點(diǎn)vj, 當(dāng)vjvi 為非零流弧時(shí)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%若收點(diǎn)vt 得到標(biāo)號或者無法標(biāo)號, 終止標(biāo)號過程if(pd)break;end %vt 未得到標(biāo)號, f 已是最大流, 算法終止dvt=d(n);t=n; %進(jìn)入調(diào)整過程, dvt 表示調(diào)整量while(1)if(No(t)0)f(No(t),t)=f(No(t),t)+dvt; %前向弧調(diào)整elseif(No(t)0&f(i,j)=0)a(i,j)=b(

43、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; %求有向賦權(quán)圖中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;endif(pd)break;end;end %求最短路的Ford 算法結(jié)束i

44、f(p(n)=Inf)break;end %不存在vs 到vt 的最短路, 算法終止. 注意在求最小費(fèi)用最大流時(shí)構(gòu)造有向賦權(quán)圖中不會含負(fù)權(quán)回路, 所以不會出現(xiàn)k=ndvt=Inf;t=n; %進(jìn)入調(diào)整過程, dvt 表示調(diào)整量while(1) %計(jì)算調(diào)整量if(a(s(t),t)0)dvtt=C(s(t),t)-f(s(t),t); %前向弧調(diào)整量elseif(a(s(t),t)dvtt)dvt=dvtt;endif(s(t)=1)break;end %當(dāng)t 的標(biāo)號為vs 時(shí), 終止計(jì)算調(diào)整量t=s(t);end %繼續(xù)調(diào)整前一段弧上的流fpd=0;if(wf+dvt=wf0)dvt=wf0-

45、wf;pd=1;end%如果最大流量大于或等于預(yù)定的流量值t=n;while(1) %調(diào)整過程if(a(s(t),t)0)f(s(t),t)=f(s(t),t)+dvt; %前向弧調(diào)整elseif(a(s(t),t)a1,1ans =cellclassa1,2ans = 1 2 2a2,:ans =abcans = 9 5 6 b=a1,1b =cellclass元胞數(shù)組：元胞數(shù)組是MATLAB的一種特殊數(shù)據(jù)類型，可以將元胞數(shù)組看做一種無所不包的通用矩陣，或者叫做廣義矩陣。組成元胞數(shù)組的元素可以是任何一種數(shù)據(jù)類型的常數(shù)或者常量，每一個(gè)元素也可以具有不同的尺寸和內(nèi)存占用空間，每一個(gè)元素的內(nèi)容也可

46、以完全不同，所以元胞數(shù)組的元素叫做元胞（cell）。和一般的數(shù)值矩陣一樣，元胞數(shù)組的內(nèi)存空間也是動(dòng)態(tài)分配的。（1）元胞數(shù)組的創(chuàng)建 a=matlab,20;ones(2,3),1:10a = matlab 20 2x3 double 1x10 double b=matlab,20;ones(2,3),1:10b = matlab 20 2x3 double 1x10 double c=10c = 10c(1,2)=2c = 10 2c(2,2)=5c = 10 2 5isequal(a,b)ans = 1whosName Size Bytes Class Attributesa 2x2 388

47、cell ans 1x1 1 logical b 2x2 388 cell c 2x2 208 cell 用cell函數(shù)創(chuàng)建元胞數(shù)組，創(chuàng)建的數(shù)組為空元胞。cell函數(shù)創(chuàng)建空元胞數(shù)組的主要目的是為數(shù)組預(yù)先分配連續(xù)的存儲空間，節(jié)約內(nèi)存占用，提高執(zhí)行效率。 a=cell(1)a = b=cell(1,2)b = c=cell(3,3)c = d=cell(2,2,2)d(:,:,1) = d(:,:,2) = whosName Size Bytes Class Attributesa 1x1 4 cell ans 1x1 1 logical b 1x2 8 cell c 3x3 36 cell d

48、2x2x2 32 cell （2）元胞數(shù)組的數(shù)據(jù)獲得從元胞數(shù)組中讀取數(shù)據(jù)，可保存為一個(gè)標(biāo)準(zhǔn)的數(shù)組或一個(gè)新的單元數(shù)組，或取出數(shù)組進(jìn)行計(jì)算。元胞數(shù)組中數(shù)據(jù)的訪問，可通過元胞內(nèi)容的下標(biāo)進(jìn)行，用元胞數(shù)組名加大括號。大括號中數(shù)值表示元胞的下標(biāo)。如a1，2表示元胞數(shù)組中第一行第二列的元胞。 a=20,matlab;ones(2,3),1:3a = 20 matlab 2x3 double 1x3 doublestr=a(1,2)str = matlabclass(str)ans =cellstr=a1,2str =matlabclass(str)ans =char（）和有著本質(zhì)的區(qū)別，大括號用于表示元胞的

49、內(nèi)容，小括號表示指定的元胞。a = 20 matlab 2x3 double 1x3 doublea2,1(2,2)ans = 0.9134a2,1(2,3)ans = 0.0975a1,2(2)ans =a使用元胞的下標(biāo)，可將一個(gè)元胞數(shù)組的子集賦值給另一個(gè)變量，創(chuàng)建新的元胞數(shù)組。 a=1,2,3;4,5,6;7,8,9a = 1 2 3 4 5 6 7 8 9 b=a(2:3,2:3)b = 5 6 8 9 c=a(1:3,2:3)c = 2 3 5 6 8 9本例使用元胞下標(biāo)的方式創(chuàng)建了新的元胞數(shù)組b和c，通過結(jié)果看出b和c就是元胞數(shù)組a的一部分。（3）元胞數(shù)組的刪除和重塑要?jiǎng)h除單元數(shù)組中

50、的行或列，可以用冒號表示單元數(shù)組中的行或列，然后對其賦一個(gè)空矩陣即可。a=20,matlab;ones(2,3),1:3a = 20 matlab 2x3 double 1x3 doublea(1,:)=a = 2x3 double 1x3 double a=20,matlab;ones(2,3),1:3;a1=a = matlab 2x3 double 1x3 doublea(1)=a = 2x3 double matlab 1x3 doublea(2)=a = 2x3 double 1x3 doublea(1,2)=? A null assignment can have only one non-colon index.a(1)=a = 1x3 double元寶數(shù)組和其他數(shù)組一樣，也可以通過reshape函數(shù)改變形狀，改變后的元胞數(shù)組與原元胞數(shù)組的元素個(gè)數(shù)相同，不能通過改變形狀來添加或刪除元胞數(shù)組中的元素。 a=cell(4,4)a = size(a)ans = 4 4 b=reshape(a,2,8)b = size(b)ans = 2 8（5）元胞數(shù)組中的操作函數(shù) cell：創(chuàng)建空的元胞數(shù)組cellfun：為元胞數(shù)組的每個(gè)元胞執(zhí)行指定的函數(shù)celldisp：顯示所有元