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

肆最短路问题及其应用莆1引言蚀图论是应用数学的一个分支,它的概念和结果来源非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题、博弈问题、,(环游世界),图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,,图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。蒅最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。袂最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。,其中对赋权图的有效算法是由荷兰著名计算机专家,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法。蚃定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。螃定义②2若图G=G(V,E)是赋权图且,,若u是到的路的权,则称为的长,长最小的到的路称为最短路。葿若要找出从到的通路,使全长最短,即。,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。薀Dijkstra算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。薈Dijkstra算法基本步骤:肈令:肄并令:{蚂对,求羀求得,使蒇令袄若则已找到到的最短路距离,否则令从中删去转1蚃这样经过有限次迭代则可以求出到的最短路线,可以用一个流程图来表示:聿羆第一步先取意即到的距离为0,而是对所赋的初值。薄第二步利用已知,根据对进行修