图论算法和其matlab程序

《图论算法和其matlab程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求单源最短路径的Dijkstra算法的Matlab程序function[dindex1index2]=Dijkf(a)M=max(max(a));pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;whilesum(pb)

2、=tb(tmpb(1));pb(temp)=1;index1=[index1,temp];index=index1(find(d(index1)==d(temp)-a(temp,index1)));iflength(index)>=2index=index(1);endindex2(temp)=index;endd;index1;index2;求任意两点间最短路的Floyd算法的Matlab程序function[D,R]=floyd(a)n=size(a,1);D=a;fori=1:nforj=1:nR(i,j)=j;endendfo

3、rk=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)1returnendn=max(max(E(:,1:2)));m=size(E,1);fori=1:nb(i)=0;forj=1:mifE(j,1)==i

4、E(j,2)=

5、=ib(i)=b(i)+1;endendendrp=rem(b,2);srp=sum(rp);switchsrpcase0,eu=1;case2,eu=0.5;otherwise,returnendifsrp==0v1=1;elsev1=find(rp);v1=v1(1);endvc=v1;m=size(E,1);E1=[E(:,1:2),[1:m]'];while~isempty(E1)evc=find((E1(:,1)==vc)

6、(E1(:,2)==vc));levc=length(evc);iflevc==1cEu=[cEu;E

7、1(evc,3)];vcold=vc;vc=sum(E1(evc,1:2))-vc;E1=E1(setdiff([1:size(E1,1)],evc),:);E2=E1(:,1:2);E2gv=E2>vcold;E2(E2gv)=E2(E2gv)-1;E1(:,1:2)=E2;ifvc>vcoldvc=vc-1;endifv1>vcoldv1=v1-1;endelsefork=1:levcE2=E1(setdiff([1:size(E1,1)],evc(k)),:);ncv=arComp(E2);nco=max(ncv);if(max

8、(ncv)==1)cEu=[cEu;E1(evc(k),3)];vc=sum(E1(evc(k),1:2))-vc;E1=E2;break;endendendendreturn求最小生成树的Prim算法的Matlab程序function[Te]=prim(a)T=[];e=0;v=1;n=size(a,1);c=2:n;forj=2:nb(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);endwhilesize(T,2)

9、e=e+b(3,i);v=b(2,i);t=find(c==b(2,i));c(t)=[];b(:,i)=[];forj=1:length(c)d=a(v,b(2,j));ifd0&a(i,j)

10、endendend[B,i]=sortrows(b',3);B=B';k=0;t=1:n;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T(:,k)=B(:,i);c=c+B(