资源描述：
《基于matlab求解最短路问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、.基于MATLAB求解最短路问题1.引言MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。通过本学期的学习了解和上机实践，已经初步掌握使用MATLAB工具解决实际问题的能力。结合运筹学课程的学习，我考虑使用MATLAB求解最短路问题，而在所有求解最短路的方法中，Dijkstra算法是最为经典的一种，因此本文主要解决在MATLAB环境下使用Dijkstra算法求解最短路。1.1提出问题设6个城市v1,v2,......,v6之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市
2、v1,那么从v1到v6应选择哪一路径使你的费用最省。1.2分析问题这属于一个典型的求解最短路的问题，图中顶点代表六个城市，边上的权数表示该段公路的长度，题目所求为从v1到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)=5;...W(3,4)=8;W(4,3
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.1Dijkstra算法介绍Dijkstra算法思想为：设G=（V，E）是一个带权有向图（也可以是无向图，无向图是有向图的特例），把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过
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的最短路径长度）。第三，以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比
5、原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。...第四，重复步骤第二步和第三步直到所有顶点都包含在S中。3.程序设计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;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;%numbero
6、fpointsinpointsetS.whileilabel(S(k))+C(S(k),Sbar(j))label(Sbar(j))=label(S(k))+C(S(k),Sbar(j));parent(Sbar(j))=S(k);endendend%Findtheminmallabel(j),jinSbar.temp=label(S
7、bar(1));son=1;forj=2:n-iiflabel(Sbar(j))
