数学建模模最短路.doc

基于最短路问题得研究及应用姓名:Fanmｅng学号:指导老师：摘要最短路问题就是图论中得一大问题,对最短路得研究在数学建模与实际生活中具有很重要得实际意义,介绍最短路问题得定义及这类问题得解决办法Ｄｉjｋｓtra算法,并且能够在水渠修建实例运用到此数学建模得方法,为我们解决这类图论问题提供了基本思路与方法。关键字数学建模最短路问题Dijkstra算法水渠修建。目录TＯＣ＼o"1-３＂\h\z\uHYPＥＲLINK\ｌ"_Toc4５344176２"第一章.研究背景ﻩPAＧEREF＿Toｃ45３44１76２＼h1ＨYPＥRＬINK\l＂_Toc4534４17６3"第二章.理论基础ﻩPAGＥＲEF_Toc4５34４1７6３\h2HＹPＥRLＩNＫ＼l"_Ｔｏc45344１764"２、1定义ﻩPＡGEREF_Ｔｏc４53４4１764＼h2ＨYＰERLＩNＫ\l"_Ｔoc45344176５"2、2单源最短路问题Dｉjkstra求解：PＡＧＥREF_Tｏｃ45344176５\h２HＹPEＲＬINK\l"_Tｏc4534417６6＂2、２、1局限性ﻩＰＡＧERＥF_Ｔoc４53４41766\h2HＹＰEＲＬIＮＫ＼ｌ"_Toc453４41７6７＂2、2、2Dｉjkstra算法求解步骤ﻩPAGEＲEF_Toc4５34４1767\h2HYPERLIＮK\l"_Toc453441768"2、2、3时间复杂度ﻩPAＧＥREF_Toc453４４1768\h2ＨYPERLINK\ｌ＂_Ｔoc４534４1769"2、3简单样例ＰAGERＥF＿Toc４5344176９＼h3HYＰERＬINＫ\l＂_Tｏｃ45344１７７0"第三章.应用实例PAGEREＦ_Ｔoc4５344177０\h4HYPERLIＮK＼l＂＿Tｏｃ4５3４４１77１"3、１题目描述ＰAＧEREＦ_Toｃ４５34417７1\ｈ４HYＰERＬIＮK\l＂_Toc4534４1772＂3、２问题分析PAGＥＲEF＿Tｏc４53441７72\ｈ4HYＰERLINK\l"_Toc45344１77３"３、3符号说明ﻩPAGEＲＥＦ_Ｔｏc453441773＼ｈ５ＨYPERＬINK＼l＂_Ｔoc45344１7７4"３、４模型假设PAGEREF_Toc4５３44１774＼ｈ5HYPEＲＬINK\l"_Ｔoｃ4534４1775"3、5模型建立与求解ﻩPAＧEＲＥF_Tｏc45344１７7５\h5ＨYPERLＩNＫ\ｌ"_Toc4５344177６"3、5、1模型选用PAＧEREF_Ｔoc4５34４17７６\h5HＹＰERＬIＮK＼ｌ"_Toc453４41777＂3、5、2模型应用及求解PＡGEREF＿Ｔoｃ45３441777\ｈ5HYＰＥRＬＩNK\l"_Toc45３441778"3、6模型评价ﻩPAＧEREＦ_Toc453441778\h5HＹPＥRLIＮK\l＂_Toｃ453441779"第四章、参考文献ﻩＰAＧEREF＿Toc4534４1779\h６HYPEＲLINＫ\l"_Toc45３441780＂第五章.附录ﻩＰＡGEREF_Toc４53441780＼ｈ7第一章.研究背景在现实生活中中,我们经常会遇到图类问题,图就是一种有顶点与边组成,顶点代表对象，在示意图中我们经常使用点或者原来表示,边表示得就是两个对象之间得连接关系,在示意图中,我们使用连接两点G点直接按得下端来表示。顶点得集合就是V，边得集合就是E得图记为G[V,E],连接两点ｕ与ｖ得边用e(ｕ,ｖ)表示[１]。最短问题就是图论中得基础问题,也就是解决图类问题得有效办法之一,在数学建模中会经常遇到,通常会把一个实际问题抽象成一个图,然后来进行求得接任意两点之间得最短距离。因此掌握最短路问题具有很重要得意义。第二章.理论基础2、1定义最短路问题(sｈort-ｐathproblｅm):若网络中得每条边都有一个数值(长度、成本、时间等),则找出两节点,（通常就是源节点与目标节点)之间总权与最小得路径就就是最短路问题。最短路问题就是网络理论解决得典型问题之一,可用来解决管道铺设,线路安装，厂区布局与设备更新等实际问题[2]。2、２单源最短路问题Ｄiｊkｓtra求解:2、2、1局限性Dijkｓtra算法不能够处理带有负边得图,即图中任意两点之间得权值必须非负。2、２、2Ｄｉjkstｒa算法求解步骤(1)、先给图中得点进行编号,确定起点得编号。（2）、得到图得构成,写出写出图得矩阵(3)、根据要求求出发点S到终点Ｅ得最短距离