实验报告4_matlab基础.doc

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

1、数学实验4实验项目名称MATLAB求最短路问题实验班级09数学1班实验人员钟浩航实验时间2011.03.10实验地点数学院机房实验目的：了解最短路问题的基木概念，理解Dijkstra算法与Floyd算法的基木思想，会用MATLAB软件包求解最短路问题。实验重点Dijkstra与Floyd算法原理与步骤实验难点Dijkstra算法与Floyd算法的MATLAB实现实验类型综合实验学时2实验原理及知识点：1、最短路问题及其算法1)基本概念2)固定起点的最fei路2、Dijkstra算法基木思路设G为赋权有向图或无向图，G边上的权均非负•对每个顶点，定义两个标记(/(v),z(v)

2、),其中：/(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)设/是使2(v)取最小值的f中的顶点,则令S=SU{V*},♦u<—V(4)若fHe,转2,否则，停止.(5)用上述算法求出的/(v)就是知到”的最

3、短路的权，从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.(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,转⑵.实验环境要求软件

4、：MATLAB6.5或以上版木硬件：P42.0以上，内存256以上实验内容及实验步骤：1、了解最短路问题;2、Dijkstra算法与Floyd算法的基本思想及算法步骤(见原理部分)3、验证：例1求下图从顶点u,到其余顶点的最短路.X叱2Xu4先写出带权邻接矩阵:21800GOoooo0oo61GOoooo0700□090005120003oo904600因G是无向图，故W是对称阵.解：迭代过程迭代次数/(«,)u2伉3^4如u61叫1234567800GO20CO□巳oc00oo88000000□GO0000000CO0010101010□0000000012121212最后

5、标记:/(v)021736912心）W]%“6u2“5W4%Matlab代码:w二[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;...8670512inf;inf1inf503inf9;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=l;whilek

6、s(j);if1(i)>l(u)+w(u,i);l(i)=l(u)+w(u,i);z(i)二u;endendendend;紀戒*11=1;fori=l:n;forj=l:k;if广二s(j);ll(i)=ll(i)；elsell(i)=inf;endendend;lv=inf;fori=l:n;iflKiXlvlv=ll(i);v二i;endends(k+l)二v;k=k+l;u二s(k);encl1z运算结果为：1=021736912z=11162545例2：见PPT4,实验作业1)验证例1、例2；2)某公司在六个城市Cl,C2,C3,C4,C5,C6屮都有分公司，从Ci到

7、Cj的直达航班票价由上述矩阵的笫i行第j列元素给出，该公司想算出一张任意两个城市Z间的最廉价路线表，试作出这样的表来。050oo4025105001520oo25co1501020□04020100102525oo20100551025oo25550实验指导情况记录:实验小结:注：实验教案必需提前备好，实验指导情况做随堂记录。