基于MATLAB求解短路问题

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

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

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

4、路径的顶点集合( 用 U 表 示)， 按最短路径长度的递增次序依次把第二组的顶点加入 S 中。在加入 的过程中，总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离， S 中的 顶点的距离就是从 v 到此顶点的最短路径长度， U中的顶点的距离， 是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。其步骤主要 有：第一，初始时， S 只包含源点，即 S顶点，v 的距离为0。U 包含 除v 外的其他顶点， U 中顶点 u 距离为边上的权(若 v 与u 有边)或(若 u 不是 v 的出边邻接点)。第二，从U 中

5、选取一个距离 v 最小的顶点 k，把k 加入S 中(该选定的 距离就是 v 到k 的最短路径长度)。第三，以k 为新考虑的中间点， 修改U 中各顶点的距离； 若从源点 v 到 顶点 u的距离(经过顶点 k)比原来距离(不经过顶点 k)短，则修改顶点 u 的距离值，修改后的距离值的顶点 k 的距离加上边上的权第四，重复步骤第二步和第三步直到所有顶点都包含在 S 中程序设计 function c0,c,path0,path=dijkstra(s,t,C,flag) s=floor(s); t=floor(t);n=size(C,1); label=ones(1,n)*inf;label(s)=0;

6、S=s;Sbar=1:s-1,s+1:n;c0=0; path=zeros(n,n); path(:,1)=s; c=ones(1,n)*inf; parent=zeros(1,n); i=1; % number of points in point set S. while i label(S(k)+C(S(k),Sbar(j) label(Sbar(j)=label(S(k)+C(S(k),Sbar(j); parent(Sbar(j)=S(k);endendend% Find the minmal label(j), j in Sbar.temp=label(Sbar(1);son=1;

7、for j=2:n-iif label(Sbar(j)V3-V2-V5-V6，结合网络图进行验证，所求即为最短路。并且利用 上述程序还可求得网络中任意两点之间的最短路径。学习体会MATLAB是美国 MathWorks公司出品的商业数学软件，用于算法开发、 数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境， 主要包括 MATLAB和 Simulink 两大部分。MATLAB是 matrix&laboratory 两个词的组合，意为矩阵工厂（矩阵实 验室）。是由美国 mathworks 公司发布的主要面对科学计算、可视化以及交 互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科

8、学数据可 视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使 用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众 多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交 互式程序设计语言（如 C、Fortran ）的编辑模式，代表了当今国际科学计 算软件的先进水平。Matlab 的学习是在运筹学之后开始的，虽然是作为选修课，也只安排 了短短的 10 次课，但从一开始学习，我就抱着要掌握好这个工具的态度上 课，因为不管是数学建模还是运筹学中，都可以用到它解决很多实际问题。 课堂上教员给我们讲解了软件的基本操作并介绍了大量常用的命令，通过 理论学习和上机实践操

9、作，慢慢的从开始的完全不懂渐渐能够编写一些简 单的 M 文件解决一些应用题，其中的成就感是相当令人欣慰的。虽然在此 之前我们还学过 C语言、 C+和数据库，也可以用它们来编程解题，但相比 之下，使用 MATLAB要简单得多，同样的一个问题，用编程的方法可能需要 编写很多条代码，在这个软件中却可以轻松实现。“师傅领进门，修行靠个人” ，受限于开课课时，教员不可能给我们做 太过深入的教学，因此要想学好这个软件，最重要的还是靠自己课下的探 索，任何工具性的东西都是这样，只有练熟才了生巧。对提高 matlab 编程能力的方法，我想主要有以下三个：、查 help在第一节课教员就向我们介绍了 help 命

10、令，在学习过程中，时常遇到 一些不知道的关键字，这时候只要通过 help 命令就可以找到该关键字的介 绍，并且还有部分举例，非常有助于理解程序。、多上论坛，搜索帖子、发帖询问网上有很多关于 MATLAB的贴吧和论坛，许多学习这个程序的人都在这里交流，有初学者也有高手，上论坛的一个好处就是可以知道别人在学习 过程中都遇到了一些什么问题，他们是怎么解决的，有什么好的学习经验 和方法可以供自己借鉴，甚至也可以自己发帖和别人交流，请教高手解答 自己的困惑等等。、阅读别人、特别是牛人的程序 多阅读程序永远是编程类软件学习的必经途径，只有通过多阅读，才 能理解算法的思想，熟悉代码的编写方法。当然了，正如所有的程序语言 一样，“3分课本 7分上机”，一定要动手才行， 不