基于MATLAB求解短路问题

1、基于MATLAB求解最短路问题日期:基于MATLAB解最短路问题1. 引言MATLAB和Mathematica、Ma pie并称为三大数学软件。它在数学类科技 应用软件中在数值计算方面首屈一指。通过本学期的学习了解和上机实践， 已经初步掌握使用MATLA工具解决实际问题的能力。结合运筹学课程的学 习，我考虑使用MATLAB解最短路问题，而在所有求解最短路的方法中， Dijkstra算法是最为经典的一种，因此本文主要解决在MATLAB境下使用 Dijkstra 算法求解最短路。1.1提出问题设6个城市V1,V2,v 6之间的一个公路网(图1)每条公路为图中的 边，边上的权数表示该段公路的长度(单

2、位：百公里),设你处在城市V1,那么 从V1到V6应选择哪一路径使你的费用最省。1.2分析问题这属于一个典型的求解最短路的问题，图中顶点代表六个城市，边上 的权数表示该段公路的长度，题目所求为从Vi到V6、的一条费用最省的路径, 我们假设所需费用仅与路径长短有关，因此求费用最省的路径即求权值最 小的路径。网络图中各权值均为正，可以使用 Dijkstra 算法。1.3数据整理将网络图中各边的权作如下整理以方便程序运行W(1,2)=5; W(2,1)=5;W(1,3)=2; W(3,1)=2;W(2,3)=1; W(3,2)=1;W(2,4)=5; W(4,2)=5;W(2,5)=5; W(5,2

3、)=5;W(3,4)=8; W(4,3)=8;W(3,5)=10; W(5,3)=10;W(4,5)=2; W(5,4)=2;W(4,6)=5; W(6,4)=5;W(5,6)=2; W(6,5)=2;2. 数学原理2.1 Dijkstra算法介绍Dijkstra算法思想为：设G= (V, E)是一个带权有向图(也可以是无向图，无向图是有向图的特例），把图中顶点集合V分成两组：第一组为 已求出最短路径的顶点集合（用 S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到 SS中。在加入中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（用U表

4、示），按最短路径长度的递增次序依次把第二组的顶点加入 的过程中，总保持从源点V到S中各顶点的最短路径长度不大于从源点 V到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从V到此顶点的最短路径长度，U中的顶点的距离，是从V 到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。其步骤主要 有:第一，初始时，S只包含源点，即S= 顶点, v的距离为0。U包含除V外的其他顶点，U中顶点u距离为边上的权（若V与u有边）或（若u 不是V的出边邻接点）。第二，从U中选取一个距离V最小的顶点k，把k加入S中（该选定的 距离就是V至咔的最短路径长度）。第三，以k为新考虑的中间点，

5、修改U中各顶点的距离；若从源点V到 顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。第四，重复步骤第二步和第三步直到所有顶点都包含在 S中。3. 程序设计functioncO,c, pathO ,p ath=dijkstra(s,t,C,flag)s=floor(s);t=floor(t);n=size(C,1);label=on es(1, n) *i nf;label(s)=0;S=s;Sbar=1:s-1,s+1: n;c0=0;p ath=zeros (n,n);path(:,1)=s;c=on es(1, n)*

6、 inf;paren t=zeros(1, n);i=1; % nu mber of points in point set S.while i<n% for each point in Sbar, rep lace label(Sbar(j) by% mi n(label(Sbar(j),label(S(k)+C(S(k),Sbar(j)for j=1: n-ifor k=1:iif label(Sbar(j) > label(S(k)+C(S(k),Sbar(j) label(Sbar(j)=label(S(k)+C(S(k),Sbar(j); pare nt(Sbar(j)=

7、S(k);endendend% Find the mi nm al label(j), j in Sbar. temp=label(Sbar(1);son=1;for j=2: n-iif label(Sbar(j)< temptemp=label(Sbar(j);so n=j;endend% up date the point set S and SbarS=S,Sbar(so n);Sbar=Sbar(1:so n-1),Sbar(so n+1: n-i); i=i+1;% if flag=1, just out put the shortest p ath betwee n s a

8、nd t. if flag=1 && S(i)=tson=t;temp_p ath=s on;if son=swhile paren t(so n)=s son=paren t(s on); temp_ path=temp_ paths on;endtemp_p ath=te mp_p ath,s;endtemp_p ath=fli plr(temp_ path);m=size(te mp_p ath,2);path0(1:m)=temp_ path;c_te mp=0;for j=1:m-1c_te mp=c_te mp+C(temp_ path(j),te mp_p ath

9、(j+1); endcO=c_te mp;p ath(t,1:m)=pathO; c(t)=cO;returnend end% Form the out put resultsfor i=1: nso n=i;temp_ path=s on;if son=swhile paren t(so n)=sson=paren t(s on);temp_p ath=te mp_p ath,s on; endtemp_p ath=temp_ paths; endtemp_ path=fli plr(temp_ path); m=size(te mp_p ath,2);p ath(i,1:m)=temp_

10、path; c_temp=0;for j=1:m-1c_te mp=c_te mp+C(te mp_p ath(j),te mp_p ath(j+1); endc(i)=c_te mp; cO=c(t);7p athO=p ath(t,:); end return4. 结果分析4.1运行程序cics=1;t=6;flag=1;W=o nes(9,9)*i nf; %for i=1:9W(i,i)=0;endW(1,2)=5; W(2,1)=5;W(1,3)=2; W(3,1)=2;W(2,3)=1; W(3,2)=1;W(2,4)=5; W(4,2)=5;W(2,5)=5; W(5,2)=5;

11、W(3,4)=8; W(4,3)=8;W(3,5)=10; W(5,3)=10;W(4,5)=2; W(5,4)=2;W(4,6)=5; W(6,4)=5;W(5,6)=2; W(6,5)=2;cO,c, pathO, path=dijkstra(s,t,W,flag); cOpathO4.2运行结果匚ommand WindowcO =10pathO =135(5由运行结果可知，从V1到V6的最短路径长度为10，路径为:V1->V3->V2->V5->V6，结合网络图进行验证，所求即为最短路。并且利用 上述程序还可求得网络中任意两点之间的最短路径。5. 学习体会MATL

12、A是美国MathWorks公司出品的商业数学软件，用于算法开发、 数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境， 主要包括MATLA和Simulink两大部分。MATLA是matrix&laboratory两个词的组合，意为矩阵工厂（矩阵实验室）。是由美国mathworks公司发布的主要面对科学计算、可视化以及交 互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可 视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使 用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众 多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统

13、非交 互式程序设计语言（如 C、Fortran ）的编辑模式，代表了当今国际科学计 算软件的先进水平。Matlab的学习是在运筹学之后开始的，虽然是作为选修课，也只安排 了短短的10次课，但从一开始学习，我就抱着要掌握好这个工具的态度上 课，因为不管是数学建模还是运筹学中，都可以用到它解决很多实际问题。 课堂上教员给我们讲解了软件的基本操作并介绍了大量常用的命令，通过 理论学习和上机实践操作，慢慢的从开始的完全不懂渐渐能够编写一些简 单的M文件解决一些应用题，其中的成就感是相当令人欣慰的。虽然在此 之前我们还学过C语言、C+和数据库，也可以用它们来编程解题，但相比 之下，使用MATLA要简单得

14、多，同样的一个问题，用编程的方法可能需要 编写很多条代码，在这个软件中却可以轻松实现。“师傅领进门，修行靠个人”，受限于开课课时，教员不可能给我们做 太过深入的教学，因此要想学好这个软件，最重要的还是靠自己课下的探 索，任何工具性的东西都是这样，只有练熟才了生巧。对提高matlab编程能力的方法，我想主要有以下三个：1、查 help在第一节课教员就向我们介绍了 help命令，在学习过程中，时常遇到 一些不知道的关键字，这时候只要通过 help命令就可以找到该关键字的介 绍，并且还有部分举例，非常有助于理解程序。2 、多上论坛，搜索帖子、发帖询问网上有很多关于MATLA的贴吧和论坛，许多学习这个程序的人都在这里交流，有初学者也有高手，上论坛的一个好处就是可以知道别人在学习 过程中都遇到了一些什么问题，他们是怎么解决的，有什么好的学习经验 和方法可以供自己借鉴，甚至也可以自己发帖和别人交流，请教高手解答 自己的困惑等等。3、阅读别人、特别是牛人的程序多阅读程序永远是编程类软件学习的