《MATLAB算法求解最短路问题》由会员分享，可在线阅读，更多相关《MATLAB算法求解最短路问题（16页珍藏版）》请在金锄头文库上搜索。
1、组合优化实验报告班级姓名学号实验名称最短路问题实验所用软件及版本Matlab R2008b实验序号:日期: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叫213w210230 y3、（4分）根据邻接矩阵A编程求解出节点1到节点2和节点3的最短路，并画出最短 路的树形图，假设如图24. （8
2、分）附件“50node.txt”（数据來源于贝尔实验室）为50个城市的坐标，编程求解 由第1个城市到其它各城市的最短路，给出最短路的树形图.3、详细设计 题11) .源代码：a = l 1;2 2.3;3.1 0.9;% node坐标矩阵plot(a(:,l),a(:,2VcO% 画图2) .运行结果：2.62.42.221.81.61.41.2 -1(8122.53.5题2(1).源代码：a = l 1;2 2.3 ;3.1 0.9;X,Y=size(a);h = meshgrid(l:X);%meshgrid是MATLAB中用于生成网格采样点的函数A= reshape(sqrt(sum(a
3、(h/:)-a(h,/:).A2,2),X/X);%A(find(A=0)=i nf% 构造权矩阵 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到所有结点的最短路径矩阵clearclca = l 1;2 2.3 ;3.1 0.9X，Y=size(a);h = meshgrid(l:X);%meshgrid是MATLAB中用于生成网
4、格采样点的函数A= reshape(sqrt(sum(a(h/:)-a(h/:).A2,2),X,X);%A(f i nd (A =0)=i n f;% 构造权矩阵 An,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);%结点的前驱，初始时，均为0Tm=zeros(n,n);%所有点从P标号变为T标号的过程矩阵P(s)=0;for i = l:n%将所有结点从P标号变为T标号的过程Pv(i)=s;%Pv具有P标号的结点T
5、v=Tmark(Tv,s);%删去具有P标号的结点Tm(s,:)=A(s，:)；for k=Pv%将具有P标号的点赋值无穷大，从而不影响后面的程序取最小值Tm(s,k)=inf;T(k)=intendfor k=Tv%次修改P标号点所对应的T标号点的T标号Tm(s,k)=Tm(s,k)+P(s);endfor k=Tvx,val】=min(T(k),Tm(s,k);T(k)=x;%二次修改P标号点所对应的T标号点的T标号if val = =2v(k)=s;%修改P标号点所对应的T标号点的前驱endendX, va I=m i n (T);% 寻找 P 标号点if x= = infbreak;e
6、nds=val;卩了乂义修改卩标号end %下面求解从sv到各点的最短路矩阵aad=zeros(l,n);%最短路临时存储向量for i = n:-l:lw=i;for k=l:n%将sv到i点的最短路倒序存储在aad中if w=0break;endaad(k)=w;w=v(w);if w=svaad(k+l)=w;break;endendfor l = l:n%将5v到i点的最短路顺序存储在D中if aad(l)=svk=l;for j = l:-l:lD(i,k)=aad(j);k=k+l;endendendaad=zeros(l/n);endg,h=size(D);for i=l:g%将
7、与最短路径无关的点赋值NaNforj = l:h%con由上面计算得到if D(ij)=0D(i,j)=NaNendendend %下面为在T标号结点集合中删除P标号的子函数function Tvad=Tmark(Tv,vm)tg = length(Tv);for i = l:tgif Tv(i)二=vm;wd = i;break;endendTvad = Tv(l/l:wd-l)/Tv(l/wd + l:tg);endplot(aUl),a(;2)，Y)hold onD(l,2) = l;for i=2:nx=;y=；x(2)=a(D(i，2),l);y(l)=a(D(i/l)/2);y(2
8、)=a(D(i；2)/2);plot(x,y，-m,)endhold offend(2).运行结果:源代码：function P,D=dijkstra_zder(Azsv)%Dijkstra法求解最短路A为邻接矩阵；%sv为寻求最短路的起始点%P为所有点的P标号，即路权值%D*sv到所有结点的最短路径矩阵clc;clear;a=load(* 50node.txt);X,Y=size(a);%N = size(A,l)h = meshgrid(l:X);%meshgrid是MATLAB中用于生成网格采样点的函数A= reshape(sqrt(sum(a(h,:)-a(h:).A2,2),XzX)
9、;%n,n=size(A);sv=l;s=sv;T=inf.*ones(l,n);%T 标号初始化P=inf.*ones(l,n);%P 标号初始化Tv=Ll:n;%具有T标号的点，初始时，所有点均为T标号v=zeros(l,n);%结点的前驱，初始时，均为0Tm=zeros(n,n);%所有点从P标号变为T标号的过程矩阵P(s)=0;for i = l:n%将所有结点从P标号变为T标号的过程Pv(i)=s;%Pv具有P标号的结点Tv=Tmark(Tv,s);%删去具有P标号的结点Tm(s,:)=A(s,:);for k=Pv%将具有P标号的点赋值无穷大，从而不影响后面的程序取最小值Tm(s,
10、k) = inf;T(k) = intendfor k=Tv%次修改P标号点所对应的T标号点的T标号Tm(s,k)=Tm (s,k) + P(s);endfor k=Tvx,val = min(T(k),Tm(s,k);T(k)=x;%二次修改P标号点所对应的T标号点的T标号if val = =2v(k)=s;%修改P标号点所对应的T标号点的前驱endendx,val = min(T);% 寻找 P 标号点if x= = infbreak;ends=val;P二X;%修改P标号end %下面求解从sv到各点的最短路矩阵aad=zeros(l,n);%最短路临时存储向量for i=n:-l:lw
11、=i;for k=l:n%将sv到i点的最短路倒序存储在aad中if w=0break;endaad(k)=w;w=v(w);if w=svaad(k+l)=w;break;endendfor 1 = l:n%将sv到i点的最短路顺序存储在D中if aad(l)=svk=l;forj=l:-l:lD(i,k)=aad(j);k=k+l;endendendaad=zeros(l,n);endg,h=size(D);for i=hg%将与最短路径无关的点赋值NaNfor j = l:h%con由上面计算得到if D(izj)=0D(ij) = NaN ;endendend%下面为在丁标号结点集合中
12、删除P标号的子函数function Tvad=Tmark(Tv/vm)tg = length(Tv);for i=l:tgif Tv(i) =vm;wd = i;break;endendTvad = Tv(l,l:wd-l),Tv(l,wd + l:tg);endplot(a(:,l),a(:,2),Y)hold onD(l,2)=l;for i = l:nx=;y=;x(l)=a(D(lJ)zl);x(2)=a(D(i,2)/l);y(l)=a(D(i#l),2);y(2)=a(D(i,2)/2);ployZ-g)endhold offend(2).运行结果:4、实验总结通过本次的实验，使我们掌握最短路Dijkustra算法求解树形图有一个节点出发，到达其它所有点的最短路问题，并且认识到计算机编程其实很不容易，想要写出一个程序并运行 需要经历许多步骤，认识到自己的不足与短处，最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短，还可以引申到其它的度量，如 时间、费用、线路容量等。最短路问题也是眼下比较热门的问题，在日常生活中应用广泛，掌握最短路问题的 mat lab算法使得我们在以后的工作及生活中能够更方便的求解实际问题有较大的帮助。5、教师评语及评分
