《图论在matlab中的实现.ppt》由会员分享，可在线阅读，更多相关《图论在matlab中的实现.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论在matlab中的实现最短路问题例 某公司在六个城市中有分公司，从ci到cj的直接航程票价记在下述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图。用矩阵 （为顶点个数）存放各边权的邻接矩阵，行向量pb、index1、index2、d分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 index2(i)存放始点到第点最短通路中第顶点前一顶点的序号；d(i)存放由始点到第点最短通路的值。DijkstraDijkstra 的的MatlabMatlab程序如下：程序如下：M=10000;M=10000;a(1,:)=0,50,M
2、,40,25,10;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a(6,:)=zeros(1,6);a=a=a+aa+a;pb(1:length(a)=0;pb(
3、1:length(a)=0;pb(1)=1;pb(1)=1;index1=1;index1=1;index2=ones(1,length(a);index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;d(1:length(a)=M;d(1)=0;temp=1;while while sum(pbsum(pb)=2)=2 index=index(1);index=index(1);end end index2(temp)=index;index2(temp)=index;endendd,index1,index2 d,index1,index2
4、 FloydFloyd算法的算法的MatlabMatlab程序如下：程序如下：clear;clear;clcclc;M=10000;M=10000;a(1,:)=0,50,M,40,25,10;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a
5、(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a(6,:)=zeros(1,6);b=b=a+a;patha+a;path=zeros(length(bzeros(length(b););for k=1:6for k=1:6 for i=1:6 for i=1:6 for j=1:6 for j=1:6 if if b(i,jb(i,j)b(i,k)+b(k,jb(i,k)+b(k,j)b(i,jb(i,j)=)=b(i,k)+b(k,jb(i,k)+b(k,j););path(i,jpath(i,j)=k;)=k;end end end end end end
6、endend b,pathb,path最小生成树问题primprim算法如下算法如下 ：clc;clearclc;clear;M=1000;M=1000;a(1,2)=50;a(1,3)=60;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a(5,6)=70;a=a;zeros(2,7);a=a;zero
7、s(2,7);a=a=a+a;a(find(aa+a;a(find(a=0)=M;=0)=M;result=;p=1;tb=2:length(a);result=;p=1;tb=2:length(a);while while length(resultlength(result)=length(a)-1)=length(a)-1 temp=temp=a(p,tb);tempa(p,tb);temp=temp(:);=temp(:);d=d=min(tempmin(temp););jb,kbjb,kb=find(a(p,tbfind(a(p,tb)=d);)=d);j=p(jb(1);k=tb(
8、kb(1);j=p(jb(1);k=tb(kb(1);result=result=result,j;k;d;presult,j;k;d;p=p,k;tb(find(tbp,k;tb(find(tb=k)=;=k)=;endend resultresultKruskalKruskal算法如下算法如下 ：clc;clearclc;clear;M=1000;M=1000;a(1,2)=50;a(1,3)=60;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(3,4)=52;a(3,7)
9、=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a(5,6)=70;i,j i,j=find(afind(a=0)&(a=M);=0)&(a=M);b=b=a(find(aa(find(a=0)&(a=M);=0)&(a=M);data=data=i;j;b;indexi;j;b;index=data(1:2,:);=data(1:2,:);loop=max(size(a)-1;loop=max(size(a)-1;result=;result=;用用 存放各边端点的信息，存放各边端点的信息，当
10、选中某一边之后，就将此边对当选中某一边之后，就将此边对应的顶点序号中较大序号改记为应的顶点序号中较大序号改记为此边的另一序号，同时把后面边此边的另一序号，同时把后面边中所有序号为的改记为。此方法中所有序号为的改记为。此方法的几何意义是：将序号的这个顶的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。缩掉，失去了被选取的资格。while while length(resultlength(result)loop)v2 if v1v2 index(find(indexindex(find(index=v1)=v2;=v1)=v2;else else index(find(indexindex(find(index=v2)=v1;=v2)=v1;end end data(:,flagdata(:,flag)=;)=;index(:,flagindex(:,flag)=;)=;endend resultresult