图论最短路径分析及应用.doc

图论最短路径分析及应用.docH京届an匕工常院BeijingInstituteofPelrochemicalTechnology最短路径问题分析及应用专 业: 信息与计算轄班 级: 同纟且成员: 2012年06月23LI•北京摘要:主要介绍最短路的两种算法,迪杰斯特Jv.(Dijkstra)及弗罗伊徳(Floyd)算法。以及这两种算法在实际问题中的应用和比较。关键词:图论,最短路径,迪杰斯特fe(Dijkstra),弗罗伊德(Floyd)最短路问题及其应用1引言图论是应用数学的一个分支,它的概念和结果来源非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题、博弈问题、,(环游世界),图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,,图论已成为解决自然科学、工程技术、社会科学、军事等领域屮许多问题的有力工具最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络屮两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如吋间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴Z屮。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。,其屮对赋权图(w..»0),该算法能够解决两指定点间的最短路,也可以求解图G屮一-特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提岀了Ford算法,它能有效地解决含有负权的最短路问题。但在现实牛活小,我们所遇到的问题大都不含负权,所以我们在(%>0)的情况下选择Dijkstra算法。定义"1若图G二G(V,E)屮各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)O定义辺若图G=G(V,E)是赋权图且W(e)>0,e€E(G),若u是叫到匕•的路”(町的权,则称W(«)为u的长,长最小的片到耳的路W(〃)称为最短路。若要找出从匕到匕的通路u,使全长最短,即minW(u)=工W(£)。,H前国内外一致公认的较好算法有迪杰斯特拉(Dijkstm)及弗罗伊徼Floyd)算法。这两种算法屮,网络被抽彖为一个图论屮定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径吋,以该矩阵为基础不断进行H标值的最小性判别,直到获得最后的优化路径。Dijkstra算法是图论屮确定最短路的基本方法,也是其它算法的基础。为了求出赋权图屮任意两结点之间的