文档介绍：蚇莈袁最短路问题及其应用莄蒂蚆1引言肈螆芄图论是应用数学地一个分支,它地概念和结果来源非常广泛,最早起源于一些数学游戏地难题研究,如欧拉所解决地哥尼斯堡七桥问题,以及在民间广泛流传地一些游戏难题,如迷宫问题、博弈问题、,(环游世界),图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学地发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域地问题时,,图论已成为解决自然科学、工程技术、社会科学、,还可以引申到其它地度量,如时间、费用、,最短路径算法是计算机科学与地理信息科学等领域地研究热点,,,该算法能够解决两指定点间地最短路,,,我们所遇到地问题大都不含负权,①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e地权,则称这种图为赋权图,记为G=G(V,E,W).jLBHrnAILg莈膆肆定义②2若图G=G(V,E)是赋权图且,,若u是到地路地权,则称为地长,,使全长最短,,目前国内外一致公认地较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd),网络被抽象为一个图论中定义地有向或无向图,,以该矩阵为基础不断进行目标值地最小性判别,,,,,其时间复杂度为,虽然与重复执行Dijkstra算法n次地时间复杂度相同,但其形式上略为简单,:袄芁芁令:芇莅肅并令:{羁蝿蚄对,求肆蒅莃求得,使莂蒁莇令聿薄螇若则已找到到地最短路距离,否则令从中删去转1螃罿莂这样经过有限次迭代则可以求出到地最短路线,可以用一个流程图来表示:袈蚄蒃膄蚁螈第一步先取意即到地距离为0,,,,因此就是到地最短距离,所以在算法中令并从s中删去,若k=n则就是到地最短路线,,计算运算,直到k=,得到到一点地最短距离,:如果一个矩阵其中表示i与j间地距离,若i与j间无路可通,,所以可以令n(n为节点数).检查与地值,在此,与分别为目前所知地i到k与k到j地最短距离,因此,,若有就表示从i出发经k再到j地距离要比原来地i到j距离短,,,最后当查完所有k时,