matlab算法求解最短路问题

《matlab算法求解最短路问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、组合优化实验报告班级姓名学号实验名称最短路问题实验所用软件及版本MatlabR2008b实验序号:日期:1、实验目的1.掌握S短路问题的一种求解算法，并能编程实现该算法.2、实验内容1.（4分）如图1所示，节点1、2、3的坐标分别为（1，1）、（2,2.3）、（3.1,0.9）,根据各节点的坐标用matlab在2维坐标上画出3个节点.图2、（4分）川matlab编程求出图1中任意两个节点之间的距离，并用邻接矩阵4存储并输出邻接矩阵A.邻接矩阵举例如下'0叫2^13w210^230y3、（4分）根据邻接矩阵A编程求解出节点1到节点2和节

2、点3的最短路，并画出最短路的树形图，假设如图24.（8分）附件“50node.txt”（数据來源于贝尔实验室）为50个城市的坐标，编程求解由第1个城市到其它各城市的最短路，给出最短路的树形图.3、详细设计题11).源代码：a=[l1;22.3;3.10.9];%node坐标矩阵plot(a(:,l),a(:,2VcO%画图2).运行结果：2.62.42.221.81.61.41.2-1(>°8122.53.5题2(1).源代码：a=[l1;22.3;3.10.9];[X,Y]=size(a);h=meshgrid(l:X);%mesh

3、grid是MATLAB中用于生成网格采样点的函数A=reshape(sqrt(sum((a(h/:)-a(h,/:)).A2,2)),X/X);%A(find(A==0))=inf%构造权矩阵A(2)运行结果:A=Inf1.64012.10241.6401Inf1.78042.10241.7804Inf题3⑴源代码：function[PzD]=dijkstra_zd(A,sv)clearclc%Dijkstra法求解最短路％A为邻接矩阵;%sv为寻求最短路的起始点%P为所有点的P标号，即路权值%D*sv到所有结点的最短路径矩阵clea

4、rclca=[l1;22.3;3.10.9][X，Y]=size(a);h=meshgrid(l:X);%meshgrid是MATLAB中用于生成网格采样点的函数A=reshape(sqrt(sum((a(h/:)-a(h'/:)).A2,2)),X,X);%A(find(A==0))=inf;%构造权矩阵A[n,n]=size(A);sv=l;s=sv;T=inf.*ones(l,n);%T标号初始化P=inf.*ones(l,n);%P标号初始化Tv=hl:n;%具有T标号的点，初始时，所有点均为T标号v=zeros(l,n);%

5、结点的前驱，初始时，均为0Tm=zeros(n,n);%所有点从P标号变为T标号的过程矩阵P(s)=0;fori=l:n%将所有结点从P标号变为T标号的过程Pv(i)=s;%Pv具有P标号的结点Tv=Tmark(Tv,s);%删去具有P标号的结点Tm(s,:)=A(s，:)；fork=Pv%将具有P标号的点赋值无穷大，从而不影响后面的程序取最小值Tm(s,k)=inf;T(k)=intendfork=Tv%—次修改P标号点所对应的T标号点的T标号Tm(s,k)=Tm(s,k)+P(s);endfork=Tv[x,val】=min([

6、T(k),Tm(s,k)]);T(k)=x;%二次修改P标号点所对应的T标号点的T标号ifval==2v(k)=s;%修改P标号点所对应的T标号点的前驱endend[X,vaI]=min(T);%寻找P标号点ifx==infbreak;ends=val;卩⑸了乂义修改卩标号end%下面求解从sv到各点的最短路矩阵aad=zeros(l,n);%最短路临时存储向量fori=n:-l:lw=i;fork=l:n%将sv到i点的最短路倒序存储在aad中ifw==0break;endaad(k)=w;w=v(w);ifw==svaad(k+l

7、)=w;break;endendforl=l:n%将5v到i点的最短路顺序存储在D中ifaad(l)==svk=l;forj=l:-l:lD(i,k)=aad(j);k=k+l;endendendaad=zeros(l/n);end[g,h]=size(D);fori=l:g%将与最短路径无关的点赋值NaNforj=l:h%con由上面计算得到ifD(ij)==0D(i,j)=NaNendendend%下面为在T标号结点集合中删除P标号的子函数functionTvad=Tmark(Tv,vm)tg=length(Tv);fori=l:

8、tgifTv(i)二=vm;wd=i;break;endendTvad=[Tv(l/l:wd-l)/Tv(l/wd+l:tg)];endplot(aUl),a(;2)，Y)holdonD(l,2)=l;fori=2:nx