数学系毕业论文网络的最短路径算法研究

《数学系毕业论文网络的最短路径算法研究》由会员分享，可在线阅读，更多相关《数学系毕业论文网络的最短路径算法研究（21页珍藏版）》请在装配图网上搜索。

1、题 目 网络的最短路径算法研究 学 院 数学与信息工程学院 专 业 班 级 学 号 学生姓名 指导教师 完成日期 摘 要在现实生活中最短路径的运用非常多，算法也很多，最短路径分析是网络分析最基本的功能之一。近年来，随着网络的不断发展，网络中的最短路径问题具有重要的理论意义和应用价值。当网络规模很大时,求解更加复杂,计算时间和所需的存储空间也大大的增加。本文讨论网络的最短路径算法及其现实问题，其中典型的最短路径算法是Dijkstra算法。Dijkstra算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。Dijkstra 算法是目前公认的较好的最短路径算法，是计算机科学

2、与地理信息科学等领域研究的热点。Dijkstra算法将网络结点分为未标记结点、临时标记结点和永久标记结点，网络中所有结点先初始化为未标记结点，在搜索过程中和最短路径结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或所有结点都成为永久标记结点才结束，这样临时结点无序地存储在无序表中，每次搜索都要遍历到表中的所有临时结点，这样势必会带来很大的计算量，给系统的应用也会带来很大不便提高算法的效率一方面可以通过对临时结点表建立索引，加快检索速度；另一方面即减少搜索的临时结点的数量，那么效率就可以大幅度的提高。在寻径时要分步由源节点

3、开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。针对如何利用Dijkstra算法来高效地查找图中任意两点之间的最短路径这一问题，应用图中各结点的出入度来简化查找两结点之间的最短路径，再利用以求出的两点之间的最短路径快速获得结点之间的最大路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。通过对Dijkstra算法的了解，能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。本文接着简单介绍了Floyd算法，又称弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。是一种动态规划算法，稠密图效果最佳，边权可正可负，此算法简单有效，容易理解，可以算出任

4、意两个节点之间的最短距离，代码编写简单。然后运用Matlab来实现了这两种经典的算法。最后将两种算法进行了一些对比，得出结论：Dijkstra算法可为任一源节点找出与其它所有节点的最短路径，当网络问题规模增大时，Dijkstra算法会使计算时间复杂度不断增大。而Floyd算法是一种动态算法，此算法简单，容易理解，可以算出任意两个节点之间的最短距离，但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。关键词最短路径；Dijkstra算法；Floyd算法；Matlab Abstract The shortest path in real life use of very large

5、, algorithms are also many, the shortest path analysis is the most basic functions of the network analysis.In recent years, as the network continues to develop, the shortest path network has important theoretical significance and application value.When the network size is large, solving the more com

6、plex, computation time and required storage space is greatly increased.This article discusses the networks shortest path algorithm and its practical problems, which the typical shortest path algorithm is Dijkstra algorithm.Dijkstra algorithm is a well-known shortest path algorithm, it can be any sou

7、rce node to all other nodes to find the shortest path. Dijkstra algorithm is better recognized as the shortest path algorithm, a computer science and geographic information science and other fields of research.Dijkstra algorithm is divided into a network node is not marked node, the temporary tag an

8、d permanently mark nodes nodes, all nodes in the network is initialized to the first unmarked node in the search process and the shortest path through the nodes connected Results point to the temporary tag nodes, each loop nodes are from the temporary tag to search for the shortest path length from

9、the source node node as a permanent marker until you find the destination node or all nodes become permanently labeled nodes Until the end, so that the temporary node to store in disorderly disorderly table, each search must traverse to the table all temporary nodes, so that would certainly bring a

10、great amount of computation, the application will be brought to the system To great inconvenience. Improve the efficiency of the algorithm one node through the temporary table indexing and the retrieval speed; the other hand, a reduction of the search the number of temporary nodes, then the efficien

11、cy can dramatically improve. In the routing step when starting from the source node to adjacent nodes, step by step expansion of the network until it contains all the node.For how to use the Dijkstra algorithm to efficiently find the map the shortest path between any two points in this problem, appl

12、y the map in and out degree of each node to simplify the two find the shortest path between nodes, and then out of use in order to the shortest path between two points quickly get the maximum path between nodes. Main features is the starting point for the center to the outer expansion, until the ext

13、ension to the end up. Dijkstra algorithm on the understanding, can come up with the optimal solution of the shortest path, but because it traverses a lot of computing nodes, so the efficiency is low.This paper then introduces the Floyd algorithm, also known as Floyd algorithm, insertion point method

14、 is given for finding a weighted graph algorithm shortest path between vertices. Is a dynamic programming algorithm, dense graph the best, the right side can be positive or negative, this algorithm is simple and effective, easy to understand, you can calculate any of the shortest distance between tw

15、o nodes, the code to write simple. Then use Matlab to achieve these two classical algorithms. Finally, some comparison of two algorithms, to a conclusion:Dijkstra algorithm can be any source node to all other nodes to find the shortest path problem when the network size increases, Dijkstra algorithm

16、 will calculate the time complexity is increasing. The Floyd algorithm is a dynamic algorithm, this algorithm is simple, easy to understand, you can calculate any of the shortest distance between two nodes, but the Floyd shortest path algorithm to calculate the time complexity is relatively high, no

17、t suitable for large data calculations.KeywordsShortest path; Dijkstra algorithm; Floyd algorithm; Matlab 目 录1. 引言12Dijkstra算法2 Dijkstra算法概述2算法描述及基本方法33Dijkstra算法案例分析6案例1：基于Dijkstra算法在物流配送中的应用6案例2：货币兑换8案例3：军事运输84求解最短路的Floyd算法95运用Matlab来进行求解10运用Matlab程序实现Dijkstra算法10用Matlab程序实现Floyd算法116结束语12参考文献14谢词

18、15网络的最短路径算法研究Network shortest path algorithm最短路径问题是网络分析中最基本的组合优化问题之一，在公交线网规划中应用十分广泛。尤其是随着我国经济的飞速发展和城市化进程的加快，城市轨道交通已进入大发展时期。轨道交通的衔接规划是基于轨道交通的发展，对其沿线的交通资源配置优化和整合，达到客运交通支援最优化。其中很重要的任务就是对现有城市公交线网进行重新规划。然而在实际进行公交线网优化设计中，最短路径模型往往无法直接应用。路径选择算法一直是计算机网络中的一个重要研究课题。它直接关系到网络效率、传输延迟和吞吐量等主要技术性能指标。随着社会的不断进步，最短路径算法

19、在人们的日常生活显得越来越重要。比如，每天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少、这是最短路径的问题；在网络路径中，怎样选择最优的路由路径，这也是最短路径问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还是最短路径问题。由此可见对最短路径问题的研究是非常有意义的。 最短路径这一重要问题早在20世纪初就已经得到人们的高度重视。当时也有许多科学家研究这一重要问题的求解方法。 但直到1959年荷兰计算机科学家Dijkstra（迪杰斯特拉）才给出这一问题求解的基本思想,并给出了算法。后来这个算法就成了众所周知的Dijkstra 算法， 也成为了一代经典。当时

20、的Dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。但是在实际生活中往往要求解决的不只是固定一点到其他点的最短路径，而是要求计算出任意两点之间的最短距离。2. Dijkstra算法 Dijkstra算法概述Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1929年提出的，因此又叫狄克斯特拉算法。是一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。其原理是每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离永远不会在被改变，因而保证了算法的正确性。不过根据这个原理

21、，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。定义：自然选择总是

22、倾向于使动物最有效地传递其基因，因而也是最有效地从事各种活动，包括使它们活动时的时间分配和能量利用达到最佳状态。 Dijkstra算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。在寻径时要分步由源节点开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。其方法是：建立一个节点集N, 开始时N 只包含源节点, 每算一步N 中增加一个相邻节点, 直到所有网络节点均进入N中后才结束计算。算法步骤如下：（1）初始化处理, 定义数组N它只包含源节点S, , 并定义距离， v为非源节点中的其它某个节点, 该距离为节点v到源节点s 的链路长度, 若v 与s直接相邻, 则有一确

23、定值, 若v与s不直接相邻, 则。（2）不断求出数组N以外的结点F，使距离最小，并将结点F加入原来的数组，对于N以外的各节点按下式:，当,则以代入原,否则维持原值不变，这一过程重复至所有节点均包含在数组N内为止。Dijkstra算法思想为：设是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径

24、长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。2.2. 算法描述及基本方法 Dijksta 算法的原理设 是一个非负权网络, 。则D 中 最短路的长满足方程: (1)如果D 中从顶点 到其余各顶点最短路的长按照大小排序为:这里 , ，则由(1) 式有 当 时, ,且,从而即所以容易证明: 的解中的是D 中最短路的长度, 。这就是Dijkstra 的理论证明。目前最短路径问题的最成熟算法是Dijkstra算法。Dijkstra算法的思想是：先

25、给赋权图的每一顶点记1个数(称标号)，临时标号(T 标号)或固定标号(P标号)。T标号表示从始点到这一点还没有寻找到最短路径；P标号则表示从始点到这一点已寻找到最短路径。计算的每一步是把某个点的T 标号变成P标号。这样一旦终点得到P标号，计算就停止。若寻求从始点到每一点的最短路径，则最多经过步计算，计算就要停止(N 是G 的顶点数)。算法步骤如下：stepl：给始点标上P 标号，给其他各点标上T 标号；step2：在所有T 标号中取出最小者，比如：，则把该点的T 标号改为P标号；step3：重新计算具有T 标号的其他各点T 标号：选 点的T标号与中较小者作为的新标号。一般情况下，设P=|具有P

26、标号，T=|具有T标号， (V为图G的顶点集合)。令。为点的P标号，于是把中的点的T标号修改为step4：重复上述步骤，直到，这时是从到的最短路径。设是有限图，如果对中任一条边l，都规定一个实数附在其上，则称G为有限权图，称为边l的权。规定(其中）, （其中）。如图下图1，。ABCDEF图 1边权图例如，一个描述各城市之间的铁路交通图，图2中的每一边可以用这条边所表示的铁路长度为其权，于是这个铁路交通图就是权图。这个铁路交通图，也可以用每条边所代表的铁路修建费用为其权，这个铁路交通图又是一个权图。可以想到，在一个权图G中，任给两点u，v，从u到v可能有好几条路，在这些路中，求出所带的权达到最小

27、那条路是有实际意义的，这就是图中求最短路问题。这条最短路所带的权称为u到v的距离，记为。显然两点间的最短路一定简单路，所以在网络中找最短路只需在简单路中找。如上图中，A到D的所有简单路有：（1）长度为6，（2）长度为13，（3）长度为3，（4）长度为14，（5）长度为10，（6）长度为13，（7）长度为14，（8）长度为12，（9）长度为17。所以A到D的最短路为；A到D的距离为3。图 2各城市之间的铁路交通图上述求最短路的方法是枚举法，对于大的复杂的图，这种方法显然是不现实的，也不易在计算机上实现。需要寻找合适的算法。再例如假设图2表示的是一个公路网，节点表示货车可以停靠的站点，边上的权表示

28、两个站点之间的距离。那么，货车从S点出发到达T点，如何选择行驶路线，使所经过的路程最短？1959年，Dijkstra给出了一个在权图中求其任意两点间最短路的算法。在介绍该算法之前我们先讨论有限权图中点到点集之间的距离：设G是有限权图，定义u0到的距离 实现上述距离的路称为u0到的最短路。不难看出上述点到点集距离的定义等价于例如在上图1中，令，则，求？设，取，则w(AC)=， 取，则，； 取，则， ；因而，A到的最短路为。当然这里的，是预先计算的，没有在这里计算。为实现这种预先的计算，必须进行迭代。Dijkstra算法恰是这种思想。即不是孤立地求有限权图中两点间的距离与最短路，而是统筹考虑，算法

29、终止时是一次性地求出某一点到所有其余各点之间的距离与最短路。3. Dijkstra算法案例分析案例1：基于Dijkstra算法在物流配送中的应用电子商务是依托于互联网和信息技术的一种新型商务活动。目前，我国的电子商务发展势头迅猛，已经成为国民经济中的重要组成部分。相对于新生的电子商务来说，物流配送出现得比较早，但是真正把它当作一个完整的系统来研究还是在20世纪50年代。在电子商务尤其是B2C业务开展之初，国内还没有一家物流公司具有电子商务的配送经验，各个电子商务公司之恩那个求助于具有国内最大覆盖的中国邮政速递公司，EMS但是在经历一段时间之后，EMS由于自身体制的僵化分割，管理无法协调，服务水

30、平无法提高，费用居高不下对很多问题都是心有余而力不足，无法满足电子商务发展的快速要求。鉴于此种情景，国内许多大型电子商务公司都在积极地寻找出路，有的自己投资组建配送队伍，但是要将自己的网点覆盖全国实在太难，投资太大有的积极寻找新近进人电子商务配送领域的配送公司，但是后者的实力和发展迅速着实无法满足需求，也有助传统的第三方物流公司，在电子商务覆盖需求如此广大，服务环节如此复杂，业务特点往往品种多、数量少、利润低等实际问题面前，传统的物流公司往往是望而却步。商品配送成本过高电子商务公司的配送不仅面向批发商和零售商，还要直接面对大批的最终消费者，况且电子商务不受时间、地域的限制，因此比较难形成集中的

31、、有规模的配送流量，由此造成配送任务复杂而琐碎，成本居高不下，降低配送服务价格，就要解决电子商务公司与物流配送企业之间在配送服务价格之间的矛盾，需要双方的共同努力。一方面电子商务公司考虑配送成本，尽量网上销售的商品控制在与物流企业协议确定的配送范围之内，并尽量使之相对集中且形成规模。另一方面，物流配送企业应积极协作，选择最短路径作为配送路径降低配送成本，并加强管理，开源节流，降低物流成本和配送服务的价格，同时还尽可能与电子商务公司建立长期稳定的协作关系，这样做有利于物流企业制定长远投资和服务计划，有利于加快新的物流配送技术的应用，加大配送渠道和设施的建设力度，最终有利于加快实现物流配送系统的信

32、息化、自动化、网络化和智能化。从长远看，有利于持续稳定地降低物流配送的成本和价格。目前关于物流配送的问题已经有很多方法，大致可分为定性和定量两大类。定性方法是指凭个人或集体的经验来做出决策，它的执行步骤一般是先根据经验评价指标对各待选中心利用评价指标进行优劣性检验，根据检验结果做出决策。定性方法的优点是注重历史经验。简单易行，其缺点是容易犯经验主义和主观主义的错误，并且当可选地点较多时不易做出理想的决策。定量方法是根据各种约束条件和所达到的目标，把选址问题转化为函数，再利用合适的算法进行求解，求出最符合条件的解即具体的地点作为配送路径，基于最短距离改进问题的算法的物流配。采用图论中的最短路径算

33、法来建立物流配送路径选择模型，它的主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点时，得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的选址位置。案例2：货币兑换若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，那么你会兑换到俄元。 城市中流

34、通着类货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编号，实数RAB，CAB表示A兑换成B的汇率和中转费用，RBA，CBA表示B兑换成A的汇率和中转费用。Nick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现。图构：将N种货币看成N个顶点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A顶点向B顶点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)RAB。注意，这里所求的是最大值，为了转化为最短路，我们可以在数字

35、前面加上一个负号。案例3. 军事运输军事运输优化有多个目标，以“最短路”为基本模型。设某部队利用公路网机动，在已知每条道路的容量及代价(距离、时间等)时，确定最优运输路线。例如，上级指挥机关需要从甲地运送一批物资到乙地，希望在现有的公路网中确定所走的路线，使距离(或时间)最短。这是一个典型的最短路问题。 最短路问题的一般性表述为：给定一个赋权图G，对给每一条边,对应权；又给定G的两个顶点、，设P是G中从到的一条路，定义P的权为P中所有边的权之和，记为。 求一条从到的最短路，即求从到的一条权最小的路，使。则称为从到的最短路，为从到的距离，记为（在有向图中，与不一定相等）。最短路问题的经典解法是D

36、ijkstra方法。4.求解最短路的Floyd算法通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵开始，递归地进行n次更新，即由矩阵，按一个公式，构造出矩阵；又用同样地公式由构造出；最后又用同样的公式由构造出矩阵。矩阵的i行j列元素便是i号顶点到j号顶点的最短路径长度，称为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为; 其状态转移方程如下： 表示i到j的最短距离 K是穷举i,j的断点初值应该为0，或者按照题目意思来做。 当然，如果这条路没有通的话，还必须特殊处理,比

37、如没有这条路。把图用邻接矩阵G表示出来，如果从到有路可达，则，d表示该路的长度；否则。 定义一个矩阵D用来记录所插入点的信息，表示从到需要经过的点，初始化。 把各个顶点插入图中，比较插点后的距离与原来的距离，如果的值变小，则。 在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。 比如，要寻找从到的路径。根据D，假如，则说明从到经过，从到经过，到直接相连，路径为，如果，说明与直接相连，如果，说明与直接相连。利用Matlab软件来进行求解，当前最流行的数学软件之一就是Matlab。它是美国MathWorks公司在1984年推出的数学软件，其具有优秀的数值计算能力和数据可视化能力

38、。该软件不但可以解决数学中的数值计算问题，还可以解决符合演算问题，并且能够方便地绘出各种图形。Maflab提供的各种函数可以避免在解决问题中做繁琐的数学推导和计算。function min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;for i=1:n if i=start label(i)=inf;end, ends(1)=start; u=start;while length(s)(label(u)+w(u,v) label(v)=(label(u)+w(u,v); f(v)=u; e

39、nd, end, end v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i=s(j) ins=1; end, end if ins=0 v=i; if klabel(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1;endmin=label(terminal); path(1)=terminal;i=1; while path(i)=start path(i+1)=f(path(i); i=i+1 ;end path(i)=start;L=length(path);pat

40、h=path(L:-1:1);function D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j;end, end, endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k);end, end, end,endif nargin=3 min1=D(start,termina

41、l); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end 本文通过对Dijkstra算法和Floyd算法的了解，加深了我对网络最短路径算法的认识，在对Dijkstra算法的认识的过程中，知道了Dijkstra算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。在寻径时要分步由源节点开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。其方法是：建立一个

42、节点集N, 开始时N 只包含源节点, 每算一步N 中增加一个相邻节点, 直到所有网络节点均进入N中后才结束计算。在这认识这种算法的过程中我发现了一些不足之处，当网络问题规模增大时，Dijkstra算法会使计算时间复杂度不断增大。在存储图形数据和运算时，需要定义的数组，其中N为网络的结点数，当网络的结点数较大时，将占用大量的计算机内存。而Floyd算法是一种动态算法，稠密图效果最佳，此算法简单有效，容易理解，可以算出任意两个节点之间的最短距离，代码编写简单，效果高于Dijkstra算法。但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。参考文献1王杰臣.GIS网络分析的图简化方

43、法研究J.测绘学报,2001,(3):263-268.2邵振峰.配电网地理信息系统中的网络重构J.测绘通报,2001,(3):103-105.3邓春燕.两种最短路径算法的比较J.电脑知识与技术,2008,(12):511-512.4 王峰,游志胜,曼丽春. Dijkstra及基于Dijkstra的前条最短路径算法在智能交通系统中的应用J.计算机应用研究,2006,23(9):203205.5王杰臣.最短路径问题的一种改进算法J.解放军测绘学院学报,1999 ,16(14):282-285.6王杰臣.图的节点弧段联合结构表示法及其在GIS 最优路径选取中的应用J.测绘学报,2000,29(1):

44、47-51.7李霖.变量查询代数及最短路径分析J.测绘学报,2000,29(1):59-63.8张锦明.利用分区思路优化拓扑关系自动生成算法J.测绘学院学报,2000,17(2):119-122.9J.湖北汽车工业学院学报,2006,20（2）:7-10.10王宏雁,徐少英.车门的轻量化设计J.汽车工程,2004,26(3):349-353.11马迅.轻型客车结构刚度与模态的有限元分析J.机械科学与技术,2002,21(1):86-88.12马迅,周坤,饶群章,等.基于有限元法的曲轴结构分析及优化J.湖北汽车工业学院学报,2005,19(3):9-13.13马迅,秦剑.制动鼓的热结构耦合分析J

45、.湖北汽车工业学院学报,2004,18(3):5-9.14凡金伟,吕康.基于Dijkstra算法在物流配送中的应用J.电脑编程技巧与维护,2009,(04):39-45.15龙光正,杨建军.改进的最短路算法J.系统工程与电子技术,2001,24(6):106-108.,分类体系与研究进展J.测绘学报,2001,30(3):269-275.17王菲.高数公路交通事故紧急救援时间模型击救援站点布局研究J.重庆交通大学,2008,15-16.18Goldbergav M. Expected performance of Dijkstra shortest path algorithmD. Princ

46、eton,Nj, USA:Princeton University,1996.19Zhan F B. Three fastest shortest path algorithms on real roadnetworksJ .Journal of Geographic Information and DecisionAnalysis,1997,1(1):69-82.20Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr 1 Efficiently publishing relational data as XML documents T

47、he VLDB Journal,2001,10:133-154.21AhujaRK，MehlhornK，Orlin J B，TarjanREFaster Algorithms for the Ahortest Path ProblemJJournal ofAssociation of Co mputing Machinery,1990,37:213223谢辞转眼间，大学四年已经接近尾声，在这大学生活中，我感受到了那种来自老师和同学们的热情和融洽，这对我融入新环境和对自己的专业产生了很大的兴趣。台州学院的老师更让我难忘，他们严谨的学术态度，幽默风趣的授课方式给我留下了深刻的影响。在这篇论文构思和写作过程中，我的指导老师老师对我的细心指导和帮助为我论文的完成打下了坚实的基础。对于我每次的疑问，老师都细心的解答并给出写作建议，并对我的论文的修改精心的指导，使得我的论文结构一步一步的完善，内容日趋丰满。还有很多同学们的大力帮助，没有老师的细心指导和同学们的帮助，这篇论文是不可能完成的。书到用时方恨少，这篇论文的写作过程中，我深感到自己水平还非常欠缺，在以后的工作生活中，继续努力，完善自己。