实验报告4 matlab基础.doc

实验报告4_matlab基础.doc:了解最短路问题的基木概念,理解Dijkstra算法与Floyd算法的基木思想,会用MATLAB软件包求解最短路问题。实验重点Dijkstra与Floyd算法原理与步骤实验难点Dijkstra算法与Floyd算法的MATLAB实现实验类型综合 实验学时 2实验原理及知识点:1、 最短路问题及其算法基本概念固定起点的最fei路2、 Dijkstra算法基木思路设G为赋权有向图或无向图,G边上的权均非负•对每个顶点,定义两个标记(/(v),z(v)),其中:/(V):(v):V的父亲点,用以确定最短路的路线算法的过程就是在每一步改进这两个标记,使最终/(、 算法步骤赋初值:令S={如},Z(wo)=OVvgS=V\5,令心)二W(uQ,v),z(v)=uQu<—w0更新/(”)、zW):VveS=V\S,^:Z(v)>/(w)+W(w,v)则令Z(v)=/(w)4-IV(w,v),z(v)=u设/是使2(v)取最小值的f中的顶点,则令S=SU{V*},♦u<—V若fHe,转2,否则,/(v)就是知到”的最短路的权,从v的父亲标记z(u)追溯到知,、 Floyd算法思想:PPT5、Floyd算法步骤:求距离矩阵;求路径矩阵;查找最短路径的方法。d(ifj),,(i,j)::带权邻接矩阵W=(vv(i,j)):对所有,丿d(i,j)lw(i,j),r(i,j)lj,k<-(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若A=v,,转⑵.实验环境要求 软件::,内存256以上实验内容及实验步骤:1、 了解最短路问题;2、Dijkstra算法与Floyd算法的基本思想及算法步骤(见原理部分)3、验证:例1求下图从顶点u,:21800GOoooo0oo61GOoooo0700□090005120003oo904600因G是无向图,:迭代过程迭代次数/(«,)u2伉3 ^4 如u61 叫1234567800GO20CO□巳oc00oo88000000□GO0000000CO0010101010□0000000012121212最后标记:/(v)021736912心)W]%“6u2“5W4%Matlab代码:w二[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;...8670512inf;inf1inf503inf9;infinfinf13046;...infinf92inf403;infinfinfinf9630]n=size(w,1);wl二