Dijkstra算法的MATLAB实现.doc

学 号： 课 程 设 计题 目Dijkstra算法的MATLAB实现学 院信息工程学院专 业通信工程班 级姓 名指导教师2012年1月9日课程设计任务书 学生姓名： 专业班级： 通信 0901班 指导教师： 工作单位： 信息工程学院 题 目: Dijkstra算法的MATLAB实现 初始条件：（1）MATLAB应用软件的基本知识以及基本操作技能（2）高等数学、线性代数等基础数学中的运算知识（3）数据结构里面关于Dijkstra算法的基本原理和思想要求完成的主要任务: 必做题：采用MATLAB选用适当的函数或矩阵进行如下计算（1）极限的计算、微分的计算、积分的计算、级数的计算、求解代数方程、求解常微分方程；（2）矩阵的最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算；（3）多项式加减乘除运算、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。选做题：Dijkstra算法的MATLAB实现时间安排：第一周，安排任务 地点：鉴主17楼实验室第1-17，周仿真设计 地点：鉴主13楼计算机实验室第18周，完成答辩，提交报告 地点：鉴主17楼实验室指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 目录摘要IAbstractII1 MATLAB的基本运算11.1 基础微积分计算11.1.1 极限的基本运算11.1.2 微分的计算11.1.3 积分的计算21.1.4 级数的运算31.1.5 求解代数微分方程31.1.6 求解常微分方程41.2 矩阵的基本运算51.2.1 矩阵的最大最小值51.2.2 矩阵的均值方差61.2.3 矩阵的转置和逆71.2.4 矩阵的行列式71.2.5 矩阵特征值的计算81.2.6 矩阵的相乘81.2.7 矩阵的右除和左除91.2.8 矩阵的幂运算91.3 多项式的基本运算101.3.1 多项式的四则运算101.3.2 多项式的求导、求根、求值运算111.3.3 多项式的部分分式展开121.3.4 多项式的拟合131.3.5 多项式的插值运算142关于Dijkstra的问题描述152.1问题的提出152.2 Dijkstra算法的算法思想152.3 Dijkstra算法的算法原理153 Dijkstra算法的设计分析173.1 Dijkstra算法部分的设计分析173.2 程序主体的设计分析174程序源代码与算法思想194.1 文件isIn.m的源代码194.2 文件default_dat.m的源代码194.3 文件input_dat.m的源代码194.4 文件menu.m的源代码204.5 文件dijkstra.m的源代码225 测试报告276 心得体会307 参考文献31摘要MATLAB的功能十分强大，在本篇中，主要分别介绍了MATLAB在高等数学中微机分的一些基本运算，线性代数中矩阵的一些基本计算以及多项式中的计算，采用具体举例，然后根据具体的例子建模，然后编写m文件，然后实际调试运行来得出结果的方式来整理报告。在报告中为了计算的方便，在矩阵那一方面，我采用事先定义的方式，便于以后计算直接提取。在多项式那一大块我也是采用这种方式。还有文中有些运算需要通过画出图形来显示运算的效果，我也适当的画了图形来显示。 此外，本篇还对Dijkstra算法用MATLAB来实现，分析了Dijkstra算法的基本思想，设计思想，以及怎么样用MATLAB来进行实现。并且对实现的结果进行了分析。关键字：基本运算 、MATLAB 、 Dijkstra算法AbstractThe function of MATLAB is very strong.The main difference I have introduced in advanced mathematics MATLAB computer points in some of the basic operations, linear algebra .Some basic calculations in the matrix and the calculation of the polynomial, using concrete examples, and then the specific .Examples of modeling, then write m file, and then to the commissioning way to organize the findings reported .In order to calculate the convenience of the report, in the matrix that one, I used the pre-defined way, to facilitate .After the calculation of direct extraction. Polynomial which is large in this way I am. There are some text.Operations need to draw a graph to show the effect of computing, I also painted the appropriate graphics to display.In addition,the main essay I have introduced used MATLAB to enforce the Dijkstra arithmetic,analysis the basic thoughts,design thoughts of the Dijkstra arithmetic and how to use MATLAB to enforce it.Besides,the essay analysis the result of it.Keywords: basic calculations，MATLAB, Dijkstra arithmetic1 MATLAB的基本运算1.1 基础微积分计算微积分的计算在工程应用上有着广泛的应用，可以说微积分的计算是数学的基础，而MATLAB关于这一点有着很好的应用，MATLAB功能强大，对于微积分也有专门的函数来进行运算，关于基础的微机分计算主要有求函数的极限，微分运算，积分运算，级数的计算，代数的求解，以及常微分方程的求解，下面对这些分别进行介绍。1.1.1 极限的基本运算MATLAB中极限函数limit格式如下：limit(F,x,a) ；limit(F,a)；limit(F)；limit(F,x,a,right)；limit(F,x,a,left)其中F表示的是函数式，x表示求极限的变量，a表示的是变量取的值，left或right表示是取左极限还是右极限。例 求 分析：这是一个典型的求极限的题目，题目中涉及了一个变量，先要对其进行定义，然后直接利用函数limit编程计算。示例程序和运行结果如下：1.1.2 微分的计算MATLAB中微分函数diff格式如下：Y = diff(X)；Y = diff(X,n)；Y = diff(X,n,dim)其中X表示待微分的变量，n表示n次微分，第三式表示沿着定维dim的n阶微分。例 求的导数分析：微分运算能直观的显示函数值的变化快慢，在平时计算中常常反映变量的变化对函数值的影响程序和运行结果如下：1.1.3 积分的计算MATLAB中积分常用函数为int，格式为：int(f,x,a,b)其中f表示待积分的函数，x表示积分变量，而a，b则分别表示积分起始终止点。例 求下列变上限积分分析：积分运算大量运用于求面积体积等，此处选用的是一个变上限积分，属于有些典型的积分例子，但任然是根据函数格式就可以写出程序。程序和运行结果如下：1.1.4 级数的运算MATLAB中级数常用函数为symsum，格式如下：r = symsum(s)；r = symsum(s,v)；r = symsum(s,a,b)；r = symsum(s,v,a,b)函数表达的意义是表达式s关于变量v从a到b求和。例 求级数 的值分析：对于级数我们最先接触的就是常数项无穷级数, 直接用symsum 函数上下限从1到9 即可。程序和运行结果如下：1.1.5 求解代数微分方程代数方程分为很多种，有简单有复杂，方法也有很多。可用MATLAB符号工具箱中的solve( )函数， MATLAB中求解代数方程常用函数solve格式如下：x,=solve(eqn1,eqn2,eqnn，x,)其中eqn表示的是式子，x等表示的是变量。例：求解方程组5x-2=18分析：为了计算的简单，这里选用了基础的一元一次方程，直接用语句描述即可。程序以及运行结果如下：1.1.6 求解常微分方程 常微分方程是指未知的一元函数以及它的某些阶的导数连同自变量都由一已知方程联系在一起的方程。dsolve的基本格式是：s=dsolve(方程1, 方程2,初始条件1，初始条件2 ,自变量)例：求解微分方程y=2+y，y(0)=0,y(0)=0的解析解分析：求解此微分方程的解析解直接采用dsolve即可。程序和运行结果如下：1.2 矩阵的基本运算矩阵在日常工程应用中也用的十分广泛，矩阵计算是线性代数中的核心内容，其对于整个数学系统的计算方面的意义是十分巨大的，集中它的基本运算包括最大值、最小值、均值、方差、转置、逆、行列式、特征值的计算、矩阵的相乘、右除、左除、幂运算等等，下面将具体介绍。矩阵的运算都是要以矩阵为基础的，本报告中决定选用一组矩阵来完成几乎全部可以完成的计算，那么首先就得生成矩阵了。1.2.1 矩阵的最大最小值MATLAB中max函数可以表示求每一列的最大值，求最小值的函数为min，那么经过分析可以知道，先求出每一列的最大值然后求出这些最大值里面的最大值，最小值也类似，下面以A矩阵为例。程序及运行结果如下： 1.2.2 矩阵的均值方差 MATLAB中求解矩阵均值的函数是mean，它的具体用法如下：mean(A,1)表示对列取平均，mean(A,2）表示对行取平均，mean(A）则默认为mean(A,1)。若要求矩阵的均值可以进行两次求平均值，这样就可以得到矩阵的平均值，或者，直接mean(A(:)，更加简便。MATLAB中求解矩阵方差的函数是var，它的常用格式是V = var(X)，如果X是一个矩阵，var(X)返回一个包含矩阵X每一列方差的行向量。与求均值不同的是，矩阵的方差不可以通过两次求方差获得，而是用var(X(:)来求得，下面的例子可以看出，通过两次求得的结果并不正确。还是以矩阵A为例，实验程序以及运行结果如下： 1.2.3 矩阵的转置和逆矩阵的转置是矩阵运算之中很重要的一个，如果A是一个实数矩阵，那么它被转置时，第1行变成第1列，第2行变成第2列，依此类推，一个mn矩阵变为一个nm矩阵。MATLAB中求转置的函数是conj，Y=conj(X)实际中求矩阵的逆要求矩阵是方阵，MATLAB中求逆的函数是inv，格式为Y = inv(X)。实验程序和运行结果如下： 1.2.4 矩阵的行列式实际中求矩阵的行列式均要求矩阵是方阵，求矩阵行列式的函数是det，格式为Y = det(X)，实验程序及运行结果如下：1.2.5 矩阵特征值的计算求矩阵的特征值和特征向量用eig函数。V,D =eig(A)产生一个矩阵A的特征值在对角线上的对角矩阵D和矩阵V，它的列是相应的特征向量，满足AV=VD，下面以矩阵A为例来演示。1.2.6 矩阵的相乘MATLAB中求矩阵的乘积直接用符号*即可，下面以A、B矩阵为例来分别演示AB与BA区别。实验程序和运行结果如下：观察运行结果可以发现，两个结果不一样，说明矩阵的相乘不满足交换律。1.2.7 矩阵的右除和左除在MATLAB中，有两个矩阵除法的符号，左除“ ”和右除“/”。MATLAB执行它们时是不同的，且在MATLAB中求解一个系统用左除比用逆和乘法所需的运算次数要少。程序以及运行结果如下： 1.2.8 矩阵的幂运算 对于二维方阵，A的p次乘方可以用Ap实现。如果p是一个正整数，那么这个幂可以由许多矩阵乘法运算定义。对于 p= 0，得到与A维数相同的同一个矩阵；当 p 0时，如果A- 1存在，可定义A p，它是与inv(A)(-p)相同。程序以及运行结果如下： 1.3 多项式的基本运算 多项式的运算，主要包括多项式加减乘除、多项式求导、求根和求值运算、多项式的部分分式展开、多项式的拟合、插值运算。1.3.1 多项式的四则运算多项式的四则运算就是包括加减乘除，其中加减运算可以直接用+、-来运算，它们的运算规则中注意要满足向量的长度相同，而乘除就得用函数了，其中乘法的计算函数是conv，它本来是卷积的意思，同时它也符合多项式函数的运算规则，除法运算是相乘的逆运算，但会有余子式。程序和运行结果如下：1.3.2 多项式的求导、求根、求值运算多项式求导数的函数是polyder，调用格式是e=polyder（c），其中c表示的是待求导的函数式，然后求根运算的函数是roots或poly，其中roots是根据函数求多项式的根，它的调用格式是h=roots（c），c代表待求根的函数式，而poly函数是根据根求函数，格式是i=poly（h），表示根据h求函数i，然后求值运算的函数是polyval，将多项式的自变量赋予值z，则调用格式是j=polyval（f，z），表示当变量是1时，函数f的结果。程序和运行结果如下：1.3.3 多项式的部分分式展开函数residue可以将多项式之比用部分分式展开，也可以将一个部分分式表示为多项式之比。其调用格式如下：r,p,k=residue(a,b)返回多项式之比a/b的部分分式展开，参照下面公式。a,b=residue(r,p,k)返回部分分式的多项式向量。程序及运行结果如下：1.3.4 多项式的拟合多项式拟合用polyfit(x,y,n)来实现，n是拟合多项式的阶次。调用函数polyfit常用格式为p = polyfit(x,y,n)，x为变量，y为函数，n为阶数。为了能形象说明问题，采用绘图来演示。实验程序以及运行结果如下： 由上面两个图对比可知，高次拟合比低次拟合效果好，更加贴近实际情况。1.3.5 多项式的插值运算插值函数通常是分段的，插值数据通过给定的数据点x，y。插值函数一般地可表示为yi=interpi（x,y,xi,method）其中i代表几维插值可取1、2,xi为插值范围内的任意点集的x坐标,yi是插值后对应数据点集的坐标,method为插值函数的类型选项，有linear为线性，也是缺省项，cubic和cubic spline为三次样条等三样。程序以及运行结果如下： 2关于Dijkstra的问题描述2.1问题的提出给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。2.2 Dijkstra算法的算法思想 按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合 （2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证： （1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。2.3 Dijkstra算法的算法原理首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D3=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为。显然，长度为 Dj=MinD | viV 的路径就是从v出发的长度最短的一条最短路径。此路径为(v,vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是Dj和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是Dj=MinD | viV-S 其中，D或者是弧(v,vi)上的权值，或者是Dk(vkS)和弧(vk,vi)上的权值之和。 迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcsLocate Vex(G,v),i viV 2）选择vj，使得Dj=MinD | viV-S 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。3 Dijkstra算法的设计分析3.1 Dijkstra算法部分的设计分析Dijkstra算法的算法步骤如下：（1） 初使时令 S=V0,T=其余顶点，T中顶点对应的距离值 若存在，d(V0,Vi)为弧上的权值 若不存在，d(V0,Vi)为 （2）从T中选取一个其距离值为最小的顶点W且不在S中，加入S （3）对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的 距离值比不加W的路径要短，则修改此距离值 重复上述步骤（2）、（3），直到S中包含所有顶点，即S=T为止思考上述算法，结合MATLAB的语言特性，我认为可以用两个数组分别表示S和T，S表示已知节点因此可以起名为know，而T起名为lengs，意为lengths，相应的，lengs(i)就代表目前已知的从V0到Vi的最短路径。接下来的问题就是如何表示两个节点之间的距离。经过查阅资料结合以前的数据结构知识可以知道表示方法有邻接表、邻接矩阵等，MATLAB语言本身最初就是用于矩阵计算，对矩阵支持有先天性的优势，因此我认为邻接矩阵是最好的表达方式。对于矩阵中的任意位置的数adj_mat(i,j)的值代表从节点i到节点j的长度。程序中默认使用的是无向图，即adj_mat(i,j)的值与adj_mat(j,i)的相等。但实际上，dijkstra对图是有向还是无向并不作要求，因此对于有向图，算法也能正确工作。不过为了输入上的简便故采用无向图。3.2 程序主体的设计分析有了运算的算法，还需要一个能把数据处理、数据传输、显示结果的界面传递的框架。由于邻接矩阵的输入并不是一件容易的事情，因此程序中提供了使用默认数据或手动输入数据两种方式。默认数据为7*7的矩阵表3-1 默认数据09966inf1315259901312688661302364inf12203775413633023121586772305625845412560 手动输入则需要先输入节点的数量n，然后手动输入(n-1)+(n-2)+1个数据，即n*(n-1)/2个数据，保证的信息的完整。遗憾的是由于对MATLAB相关函数不太熟悉，并不能提供从文件读取输入的功能。界面采用简单的菜单式界面，在MATLAB的主窗口中显示。同时为了便于用菜单调用输入、计算等的函数，将各个板块的功能编写为独立的.m文件，文件列表及功能如下表3-2：表3-2文件及文件作用对应表menu.m显示菜单并对其他函数执行调用，程序的入口dijkstra.m通过已有的数据进行dijkstra算法并返回结果的函数，是计算的核心。isIn.m在dijkstra算法中需要判断一个节点是否是已知节点，该文件中存放的即为执行判断的函数default_dat.m用存放的默认的数据生成邻接矩阵并返回input_dat.m让用户输入数据并生成邻接矩阵并返回同时程序还集成了一定的错误处理功能，如在输入查询最短路径的起始地址和目的地时，程序会判断起始地址与目的地址是否相等，如果相等则会输出错误信息，但是同时，程序的错误处理并不强，例如输入起始地和目的地可能造成数组越界、菜单选择错误、不存在从出发点到达目的的路径时程序会访问错误的地址之类的错误并没有处理。由于错误产生的情况多种多样，而最近又比较忙，因此并没有把程序做得尽善尽美，而是保证了在输入正确的情况下程序的计算结果不会出错。4程序源代码与算法思想4.1 文件isIn.m的源代码isIn函数接受2个参数，第一个为数组，第二个为数字，函数的功能为查看数字是否在数组中。函数的返回值为0或者1,1代表数字在数组中出现过，0代表并未出现。function count = isIn(array , num)k = length(array);count = 0;for j = 1:1:k if array(j) = num count = 1; endend4.2 文件default_dat.m的源代码default_dat函数不需要参数，直接返回存放默认数据的矩阵，代码为普通赋值语句，故不附代码，默认数据参见3.24.3 文件input_dat.m的源代码input_dat.m与default_dat.m一样为生成数据的代码，故与default_dat.m一样不需要参数，只返回矩阵。代码如下：function adj_mat = input_dat()length = input(请输入结点数量：);adj_mat = zeros(length);for i = 1:1:length for j = i:1:length if i = j fprintf(请输入结点%d到结点%d的长度(没有则输入0),i,j) adj_mat(i,j) = input(:); if adj_mat(i,j) = 0 adj_mat(i,j) = inf; end adj_mat(j,i) = adj_mat(i,j); end endend运行时首先要求输入矩阵的大小，存放在变量length中，然后根据length生成相应大小的矩阵，之后要求用户一个个输入数据。4.4 文件menu.m的源代码menu.m为整个程序各个模块的连接者，同时是程序的入口和出口，故不需要任何的参数和返回值。代码如下：function menu()choice = 1;adj_mat = ;while choice = 5 choice = input(欢迎来到dijkstra算法求取最短路径系统！n请选择:n1.使用默认数据 2.输入数据n 3.查看数据 4.求取路径n5.退出程序n); if choice = 1 adj_mat = default_dat(); fprintf(已启用默认数据n); elseif choice = 2 adj_mat = input_dat(); elseif choice = 3 disp(adj_mat); elseif choice = 4 sta = input(请输入起始结点:); dst = input(请输入目的地:); if sta = dst fprintf(起始结点与目的结点不能相同！rn); else leng , path = dijkstra(adj_mat , sta , dst); fprintf(最短路径为：%dn,leng); k = length(path); fprintf(经过路径为:); for i = 1:1:k-1 fprintf(%d -,path(i); end fprintf(%dn,path(k); end endendmenu.m涉及较多的输入与输出。其中输入主要使用input函数，而输出主要使用fprintf函数。fprintf函数与C语言的printf函数比较类似，可以很方便的将数字格式化到字符串中输出。在用户不输入退出且输入不出错的情况下，菜单会多次的输出。menu.m中维持了一个adj_mat变量来保存邻接矩阵，在不同的选项中提供对adj_mat不同的操作。菜单主要提供如下几个功能：使用默认数据：选择的情况下会使用默认数据覆盖当前数据（即将默认数据的值写入adj_mat)。输入数据：选择的情况下会调用input_dat函数接受用户的输入并保存到adj_mat中。查看数据：输出adj_mat的值。调用dijkstra算法：输入用户拟定的起始地点sta和目的地dst，并将adj_mat传入dijkstra函数进行运算。结果为两个值：leng(长度）和path（路径），更详细的说明参见4.5。退出程序：提供正常结束程序，返回一般的MATLAB脚本。附：menu.m中的算法流程图 图4-1 menu中的算法流程图4.5 文件dijkstra.m的源代码dijkstra.m中存放的是整个程序的核心算法，即迪杰斯科拉算法的MATLAB实现版本，函数接受三个参数：第一个参数为邻接矩阵，第二个参数为起始结点的标号，第三个参数为目的结点的标号。函数的返回值有两个，第一个为最短路径的长度，第二个为最短路径途径的结点数组，将该数组顺序输出则可输出最短路径经过的所有结点（包括起始结点和目的结点）。代码如下：function leng,path = dijkstra(adj_mat , sta , dst)m = length(adj_mat);lengs = linspace(0,0,m);paths = linspace(0,0,m);know = linspace(0,0,m);know(1) = sta;k=1;for i = 1:1:m if i = sta lengs(i) = adj_mat(sta,i); if lengs(i) = inf paths(i) = sta; end endendindex = 1;for i = 1:1:m if i = sta min = inf; for j = 1:1:m count = isIn(know,j); if count = 0 & lengs(j) = min k = j; min = lengs(j); end end know(index) = k; index = index+1; for j = 1:1:m count = isIn(know,j); if count = 0 & (lengs(i) + adj_mat(i,j) 5-2,则paths(2) = 5 , paths(5) = 1。这样在输出从i到j的路径时，可以由j开始逆向寻找，输出查看.paths(paths(j).的值，直到值为i时停止查找，即为数据结构中的“静态链表”，这样的好处是对应每个结点只需要一个数就可以表示最短路径的字符串，便于存储，但是要注意解析时需要逆向解析。（2） 接下来查看邻接矩阵，如果存在从起始结点到结点i的路径，则将lengs(i)的值更改为矩阵中的值，并将paths(i)更改为目的地。（3） 寻找在lengs中且不在know中最小的值（即未知结点中路径最短的值），将对应的结点i加入know中，用i来判断，对于每个不在know中的结点j,如果lengs(i) + adj_mat(i,j) j)时的数据：输入完成后查看数据是否被正确存储，可以看到结果是正确的（inf是MATLAB中设定的无穷大常数，在这里代表不存在路径）：进行多次求最短路径验证，可以看到结果均正确：测试结束。多次测试结果均为正确，可以认为程序的算法是正确的，程序的结构是可靠的。6 心得体会 接触MATLAB已经有不短的时间了，以前就听说它的功能十分强大，不过没有做什么实验，也没有深刻体会到这一点，最多就只是有针对性地看一下书上的源程序，然后抄上去，看看运行结果，能出来跟书上一样的结果就已经很开心了，后来渐渐觉得MATLAB在工科上似乎是无所不能，功能十分强大，可是也没有很正式学习。对MATLAB基本运算的学习让我体会到了它在处理矩阵以及行列式这方面的独到的优点，基本运算看起来还是很简单的，不过很多细节还是不容忽视，或许，越是简单的东西越能检测一个人的能力，因为它考验了一个人的细心程度，并且，急功近利是不能够做好的，从最初步的渐渐开始，一步一步的学习，也使得我对MATLAB的基本运算有了初步的了解，并能够编写简单的函数来加以运用。以前在学习数据结构的时候，就了解了关于最短路径算法的相关知识，所以，这次看到有这个题目，我就想试着做一做。查阅了以前的数据结构书籍以及MATLAB相关的内容之后，我就开始写程序了，在网上可以找到很多这样的程序，不过，都或多或少有些毛病，所以还不如自己把算法思想研究透了，自己来写。我实现的时候，把它做成了简单的菜单形式，通过输入选择来实现，同时，还在内部设置了一组默认数据，可以方便老师来进行测试，结果在MATLAB主窗口输出。在调试验证过程中，也出现了很多问题，最开始的时候，发现有的输出的结果并不是最短的，因而，我只好再对程序进行认真的检查，修改。几经努力，最后终于得到了完善，看到了那些正确的输出结果，很有成就感。总之，这次课程设计让我收获了很多，不仅对MATLAB的基本运算有了初步的认识，还对Dijkstra算法有了更深刻的认识和理解，自己认真独立完成了一件事，让我觉得有了很大的成就感，MATLAB强大的功能我只学习了冰山一角，但是，我相信，努力过了总会有收获的。 7 参考文献1.MATLAB从入门到精通周建兴编著，人民邮电出版社2.精通MATLAB 7王正林, 刘明编著，北京-电子工业出版社3.MATLAB语言及其在电子信息工程中的应用 王洪元编清华大学出版社4.数据结构（C语言版） 严蔚敏编 北京-清华大学出版社5.百度百科 Dijkstra算法 /view/7839.htm袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄