实验教案4 matlab基础.doc

《实验教案4 matlab基础.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学建模教案4实验项目名称MATLAB求最短路问题实验班级06数本1、2班实验人数实验时间第9周周四5〜8节实验地点科技楼1611实验目的：了解最短路问题的基木概念，理解Dijkstra算法与Floyd算法的基木思想，会用MATLAB软件包求解最短路问题。实验重点Dijkstra与Floyd算法原理与步骤实验难点Dijkstra算法与Floyd算法的MATLAB实现实验类型综合实验学时2实验原理及知识点：1、最短路问题及其算法1)基本概念2)固定起点的最fei路2、Dijkstra算法基木思路设G为赋权有向

2、图或无向图，G边上的权均非负•对每个顶点，定义两个标记(/(v),z(v)),其中：/(V):表从顶点Uo到V的一条路的权.z(v)：V的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终/(巧为从顶点U0到V的最短路的权.3、算法步骤(1)赋初值:令S={如},Z(wo)=OVvgS=V5,令心)二W(uQ,v),z(v)=uQu<—w0(2)更新/(”)、zW)：VveS=VS,^:Z(v)>/(w)+W(w,v)则令Z(v)=/(w)4-IV(w,v),z(v)=u(3)设/

3、是使2(v)取最小值的f中的顶点,则令S=SU{V*},♦u<—V(4)若fHe,转2,否则，停止.(5)用上述算法求出的/(v)就是知到”的最短路的权，从v的父亲标记z(u)追溯到知，就得到心到v的最短路的路线.4、Floyd算法思想：PPT5、Floyd算法步骤：1)求距离矩阵；2)求路径矩阵；3)查找最短路径的方法。d(ifj),，到丿的距离.r(i,j)：i到丿2间的插入点.输入：带权邻接矩阵W=(vv(i,j))vxv.(1)赋初值：对所有，丿d(i,j)lw(i,j),r(i,j)lj,k<-1

4、.(2)更新d(i,j),r(i,j):对所有乙丿，若d(i,k)+d(k,j)〈d(i,j),则d(i,j)ld(i,k)+d(k,j),T(i,j)jk(3)若A=v,停止.否则kJkH,转⑵.实验环境要求软件：MATLAB6.5或以上版木硬件：P42.0以上，内存256以上实验内容及实验步骤：1、了解最短路问题;2、Dijkstra算法与Floyd算法的基本思想及算法步骤(见原理部分)3、验证：例1求下图从顶点u,到其余顶点的最短路.X叱2Xu4先写出带权邻接矩阵:21800GOoooo0oo61GO

5、oooo0700□090005120003oo904600因G是无向图，故W是对称阵.解：迭代过程迭代次数/(«,)u2伉3^4如u61叫1234567800GO20CO□巳oc00oo88000000□GO0000000CO0010101010□0000000012121212最后标记:/(v)021736912心）W]%“6u2“5W4%Matlab代码:w二[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;...8670512inf;inf1inf

6、503inf9;infinfinf13046;...infinf92inf403;infinfinfinf9630]n=size(w,1);wl二w(l,:);力赋初值fori=l:nl(i)=wl(i);z(i)=l;ends=[];s⑴二1;U=s(l);k=l1zwhilekl(u)+w(u,i)l(i)=l(u)+w(ii,i);z(i)=u;endendendend1%求「*11=1;fori=l:nfo

7、rj二1:kifi~=s(j)ll(i)=ll(i)；elsell(i)=inf;endendendlv=inf;fori=l:nifll(i)

8、线表，试作出这样的表来。注：实验教案必需提前备好，实验指导情况做随堂记录。