最短路径问题的算法分析及建模案例

最短路径问题的算法分析及建模案例最短路径问题的算法分析及建模案例TOC\o"1-3"\h\u12477一.摘要 38159二.网络最短路径问题的基础知识 58582.1有向图 719722.2连通性 错误!未定义书签。271242.3割集 错误!未定义书签。169532.4最短路问题 85517三．最短路径的算法研究 错误!未定义书签。152563.1最短路问题的提出 930853.2Bellman最短路方程 错误!未定义书签。109753.3Bellman-Ford算法的基本思想 错误!未定义书签。220253.4Bellman-Ford算法的步骤 错误!未定义书签。217903.5实例 错误!未定义书签。204383.6Bellman-FORD算法的建模应用举例 错误!未定义书签。191263.7Dijkstra算法的基本思想 9246233.8Dijkstra算法的理论依据 9307003.9Dijkstra算法的计算步骤 9104763.10Dijstre算法的建模应用举例 10274473.11两种算法的分析 错误!未定义书签。109151.Diklstra算法和Bellman-Ford算法思想有很大的区别 错误!未定义书签。1767Bellman-Ford算法在求解过程中，每次循环都要修改所有顶点的权值，也就是说源点到各顶点最短路径长度一直要到Bellman-Ford算法结束才确定下来。 错误!未定义书签。230862.Diklstra算法和Bellman-Ford算法的限制 错误!未定义书签。166613.Bellman-Ford算法的另外一种理解 错误!未定义书签。244144.Bellman-Ford算法的改进 错误!未定义书签。摘要近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的一个典型例子。由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究，使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题图11.1图图G是一个（无向）图，其中有序二元组（V,E），V=｛，,...｝是顶点集，E=｛｝是集，是一个无序二元组{，}它表示该边连接的是顶点，。图1就是一个图。注释：图形的大小，位置，形状是无关紧要的。若={,}则称连接和；点和称为的顶点，和是邻接的顶点；如果两条边有公共的一个顶点，则称这两边是邻接的。1.2无环图定义：没有环的图称之为无环图。1.3简单图定义：没有环且没有重边的图称之为简单图。设G=（V,E）是一个简单图，则有|E|不大于|V|（|V|-1）/21.4完全图定义：若上式的等号成立那么该图中每对顶点恰好有一条边相连，则称该图为完全图。1.5有向图定义：一个有向图G是一个有序二元组（V,A），V=｛，，...,｝是顶点集，A=｛｝称为G的弧集，为有序二元组。称为连向的弧，为的出弧，的入弧；称为的得尾，称为aij的头；称为的前继，称为的后继。图2就是一个有向图。图21.6环定义：头尾重合的弧称为环。1.7简单有向图定义：没有环和重弧的有向图称为简单有向图。1.8完全有向图定义：设G=（V,E）是一个简单有向图，则|A|不大于|V|（|V|-1），若等号成立则称这样的图为完全有向图。1.9途径，迹，路定义：设图G=（V,E），若它的某些顶点与边可以排成一个非空的有限交错序列（，，,...,）,这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称之为路。显然路必为迹，但反之不一定成立。1.10连通图定义：图G中如果存在一条从顶点到的途径，则称和是连通的。如果图G中任何两个顶点都是连通的，则称G是连通图。1.11有向途径定义：设有一个有向图G=（V,A），G中某些顶点与弧组成的非空有限序列（，，，，...，，）这里，...，V，A，且=（，），则称它为从到的有向途径。类似的可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路（圈）等。当G时简单有向图时，从到的一条有向途径可简记为（，...,）。二最短路问题定义：所谓最短路径是指如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一跳有向路径使得沿这条路径上各弧的权值总和最小。2.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡，因为他害怕乘坐飞机，因此要选择一条航线，使得在空中飞行的时间尽可能的少。如何选择航线以达到要求。为此构造一个无向网络总可以化成有向网络。设G=（V,A,w）是一个有向网络，p为G中一条有向路，称w（P）=为路径p的路长。现找网络中一条从指定顶点vi到另一个指定顶点vj的最短有向路径。三最短路径算法研究3.1Dijkstra算法3.11Dijkstra算法的基本思想对网络中每个顶点赋一个标号，用来记录从顶点到该顶点的最短路的长度（称为永久标号）或最短长度的上界（称为临时标号）。算法开始时，只有顶点被赋予永久标号=0，其他顶点赋予临时标号。一般的，算法在被临时标号的顶点中寻找一个顶点，其临时标号最小，然后将赋予永久标号，并且对其余临时标号的顶点vj按照方式修正其标号。算法在所有顶点被赋予永久标号时结束。3.12Dijkstra算法的理论依据对于S中任意一顶点，其永久标号都是从顶点到该顶点的最短路的长度。对于R中任意一顶点，其临时标号都是从顶点出发，只经过S中顶点到达该顶点的最短路的长度。3.13Dijkstra算法的计算步骤最短路径问题是指在一个赋予权值的图的两个指定节点和v之间找出一条具有最小权值的路。Dijkstra算法是一个解最短路径问题的算法，这个算法不仅可以找到最短的（，v），路径而且可以给出从到图中所有节点的最短路径，基本步骤如下：设=0，对所有节点来说，设=，并且将标号为0，→t，d为和w之间的权值（距离）。按照每个没有标号的节点w计算，，表示节点t到节点w之间的权值。如果标号被修改了说明在当前得到的到w的最优路径上t和w相邻，用记录下来在所有中选择一个最小的即，w未标号。将s标号为/，表示节点到s的最优路径的长度且与s相邻。如果重点v已经标号，则停止。得到一条从到v的最优路径。否则s→t，反向。按照上述步骤继续计算。3.14Dijstre算法的建模应用举例某城市要在该城市所辖的8个区中的区建立一个取水点，如图所示的是这8个区之间的分布以及相邻各区的距离。现要从区向其他各区运水，求出区到其他各区的最短路径。先写出带权邻接矩阵：W=因为G是无向图，所以W是对称矩阵。迭代次数1020218328104831058610126710127912812最后标记L（v）021736912Z（v）因此得到最短路径为：迭代次数最后标记L（v）021736912Z（v）由上表可得到到各点的最短路径为：；；，，；；；，，；，。上述Dijkstra算法的MATLAB代码：w=[0218infinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);%赋初值%fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;whilek<n%更新l(v)和z(v)%fori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendl,z%求v*L1=1;fori=1:nforj=1:kifi~=s(j)l1(i)=l1(i);elsel1(i)=inf;endendendlv=inf;fori=1:nifl1(i)<lvlv=l1(i);v=i;endendlv,vs(k+1)=vk=k+1u=s(k)endl,z3.2FLOYD算法3.21FLOYD算法的基本思想直接在图的带权邻接矩阵中使用插入顶点的方法依次构造出n个矩阵，...，，使得最终得到的矩阵成为图的距离矩阵，并且同时求出插入的点的矩阵以便于得到两点间的最短路径。3.22FLOYD算法原理（1）FLOYD算法求路径矩阵的方法：在建立距离矩阵的同时可建立路径矩阵R。每一次求到一个时，按照下列的方式产生相应的新，即当被插入在任何两点间的最短路径时，被记录在中，依次求时求得，可由来查找任何两个点之间的最短路径。（2）FLOYD算法查找最短路径的方法：如果，那么点是点到点的最短路的中点。用同样的方法再查找，如果：（1）向点查找得：，，...，。（2）向点查找得：，，...，。那么从点到的最短路径为：，,...,，，，，...，，3.23FLOYD算法的算法步骤Floud算法算法目的：求任意两个顶点间的最短路径。：表示到之间的距离。：表示到之间的插入点。起始：选定带权值的邻接矩阵（1）赋值：对所有的，，，，1。（2）更新，对所有的，，如果，那么，。（3）如果=，那么算法终止；否则，再次回到（2），以此类推。3.24FLOYD建模应用举例某个城市要建立一个消防站，为该城市所属的七个区服务，如图所示。问应该把这个消防站设置在哪个区，才能使该消防站到最远的区的路径最短。用Floyd算法求出各点之间的距离，得到表格：0351075.57302742.54520524.5610750378.57423045.55.52.54.57401.57468.55.51.50从上表可以得出距离矩阵计算在各点设立服务设施的最大服务距离，。，，，，，，由于=那么应该将消防站设置在处。上述Floyd算法的MATLAB算法代码为：clear：w=[0,3,inf,inf,inf,inf,inf;3,0,2,inf,1.8,2.5,inf;inf,2,0,6,2,inf,inf;inf,inf,6,0,3,inf,inf;inf,1.8,2,3,0,4,inf;inf,2.5,inf,inf,4,0,1.5;inf,inf,inf,1.5,0];[d,r]=floyd(w)S=max(d’)%求矩阵各列的最大值s=min(S)3.