资源描述：
《最短路径学年论文及说明》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、////摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab目录摘要·······························································11引言······························································12最短路···············
2、·············································22.1最短路的定义··············································22.2最短路问题常见算法···········································23Dijkstra算法······················································23.1Dijkstra算法描述·····················
3、························23.2Dijkstra算法举例·············································33.3算法的正确性和计算复杂性······································53.3.1贪心选择性质·············································53.3.2最优子结构性质···········································63.3.3计算
4、复杂性··············································74Floyd算法··················//·······································74.1Floyd算法描述·················································84.2Floyd算法步骤················································114.3Floyd算法举例······
5、··········································115Dijkstra算法和Floyd算法在求最短路的异同··························116利用计算机程序模拟算法·············································117附录·······························································118论文总结·····························
6、······························139参考文献···························································131引言最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。//最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路
7、径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。2最短路2.1最短路的定义对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的
8、最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的的情况下选择Dijkstra算法。定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。定义2若图G=G(V,E)是赋权图且,,假设[i,j]的权记为,若i与j之间没有边相连接，那么。路径P的定义为路径中各边的长度之和，记W（
