最短路径算法及其应用

《最短路径算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖北大学本科毕业论文（设计）湖北大学本科毕业论文（设计）题目最短路径算法及其应用姓名学号专业年级指导教师职称2011年4月20日III湖北大学本科毕业论文（设计）目录绪论…………………………………………………………………………………(1)1图的基本概念………………………………………………………………………(1)1.1图的相关定义…………………………………………………………………(1)1.2图的存储结构…………………………………………………………………(2)1.2.1邻接矩阵的表示………………………………………………………(2)1.2.2邻接矩阵的相关结论………

2、…………………………………………(3)2最短路径问题………………………………………………………………………(3)2.1最短路径………………………………………………………………………(4)2.2最短路径算法…………………………………………………………………(4)2.2.1Dijkstra算法……………………………………………………………(4)2.2.2Floyd算法………………………………………………………………(5)3应用举例……………………………………………………………………………(5)3.1Dijkstra算法在公交网络中的应用……………………………………

3、………(5)3.1.1实际问题描述……………………………………………………………(5)3.1.2数学模型建立……………………………………………………………(5)3.1.3实际问题抽象化…………………………………………………………(6)3.1.4算法应用…………………………………………………………………(6)3.2Floyd算法在物流中心选址的应用…………………………………………(7)3.2.1问题描述与数学建模……………………………………………………(7)3.2.2实际问题抽象化…………………………………………………………(7)3.2.3算法应用…………………

4、………………………………………………(8)参考文献……………………………………………………………………………(10)附录…………………………………………………………………………………(11)III湖北大学本科毕业论文（设计）最短路径算法及其应用摘要最短路径算法的研究是计算机科学研究的热门话题，它不仅具有重要的理论意义，而且具有重要的实用价值。最短路径问题有广泛的应用，比如在交通运输系统、应急救助系统、电子导航系统等研究领域。最短路径问题又可以引申为最快路径问题、最低费用问题等，但它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra和Floyd

5、算法是目前最短路径问题采用的理论基础。本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际问题。【关键字】最短路径Dijkstra算法Floyd算法图论III湖北大学本科毕业论文（设计）ShortestpathalgorithmsandtheirapplicationsAbstractTheresearchabouttheshortestpathisahotissueincomputerscience.Ithasbothimportanttheoreticalsignificanceandimportantutilit

6、yvalue.Theshortestpathproblemhasbroadapplicationarea,suchastransportsystem,rescuesystem,electronicnavigationsystemandsoon.Theshortestpathproblemcanbeextendedtotheproblemofthefastestpathproblemandtheminimumcostproblem.Buttheircorealgorithmsareallboththeshortestpathalgorithms.Theclass

7、icalalgorithmsfortheshortestpath——DijkstraandFloydarethetheoreticalbasisforsolvingtheproblemsoftheshortestpath.ThearticlemainlythroughthedemonstrationandanalysisoftheDijkstraandFloydalgorithms,thenusethealgorithmstosolvethetwosimplepracticalproblems.【keywords】shortestpathDijkstraalg

8、orithmFloydalgorith