-王海霞-最短路问题及其应用

《-王海霞-最短路问题及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路问题及其应用最短路问题是图论中的一个基本问题.在赋权图中,每条边都有一个数值(长度、成本、时间等),找出两节点之间总权和最小的路径就是最短路问题.1．最短路定义1.1定义：两点之间的距离,其中为到的路的长度.达到的路为从到的最短路.例1：设图,图1则,,,其中,：是最短的.1.2构造一个图,每条边,赋予一个“权重”,得到加权连通图.例2：设图,图2则,到无直达路径,则.在初步认识了最短路问题后,我们自然会想到如何求最短路.下面我将介绍几种求最短路的方法.2.最短路问题算法对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图的有效算法是由荷兰著名计算机专家Dijkstr

2、a在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图中一特定点到其它各顶点的最短路.后来海斯在Dijkstra算法的基础之上提出了海斯算法.但这两种算法都不能解决含有负权的图的最短路问题.因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题.但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法.这是一个公认的好算法.所谓好算法,就是完成算法所耗用的时间不超过事先给定的以图的顶点与边数为变量的一个多项式.下面我着重介绍下Dijkstra算法.Dijkstra算法：（1）不相邻时,取.（2）令；,；,.（3）对每个,用替代

3、；设是使取最小值的中的项,令.（4）,止；若,用代替,转（3）.容易看出,算法中的就是到的距离.由于图是有限图,故有限步骤之后,可以逐次得出到每个顶的距离,即求得顶到各顶的最短轨之长,而且还可以在算法的执行中标志出从到各顶的一条最短轨.例3：设图,图3问：及相应的路（最短路）.（方法一）计算：,；,；……这样尝试计算每一条路,最终取最短路即可.但是这个方法工作量较大.下面介绍另一种方法——标号：,从到的最短路：,其中,是到的最短路.这说明了.（方法二）（标号）Step1.取,,由,将并入中,作,.Step2.,Step3.取,……如此类推做下去,即可得到最短路.如求例3中到其余各点的最短路

4、：用标号的方法在具体做题时只要：除起点外,给每个点赋予一个充分大的数,例如在本例中赋值,修改的标号为,修改的标号为,修改的标号为,则修改的标号为,……依次将每一个点的标号都降到最低,而每一个点的标号即为到的最短路.如下图所示：图43最短路的应用3.1在运输网络中的应用④设6个城市之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市,那么从到应选择哪一路径使你的费用最省.解：除点外，给其余每一个点附一个充分大的数，不妨在本例中赋值1000，修改的标号为，修改的标号为，则修改的标号为，则修改的标号为，则修改的标号为，则修改的标号为，则修改的标号

5、为，如此，的标号最小是10，即到的最短路为10.3.2其他应用l最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。l在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发

6、犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的．4结语本文将最短路理论应用到实际生活中，尤其是在网络运输和舰船通道路线中的应用具有很重要的意义。将提高实际生活的效率，同时也凸显出学习和应用最短路问题原理的重要性。另外，最短路问题在城市道路

7、建设、物资供应站选址等问题上也有很重要的作用，分析和研究最短路问题趋于热门化。