《数学系毕业论文网络的最短路径算法研究》由会员分享，可在线阅读，更多相关《数学系毕业论文网络的最短路径算法研究（21页珍藏版）》请在金锄头文库上搜索。
1、题 目 网络的最短路径算法研究 学 院 数学与信息工程学院 专 业 班 级 学 号 学生姓名 指导教师 完成日期 V摘 要在现实生活中最短路径的运用非常多，算法也很多，最短路径分析是网络分析最基本的功能之一。近年来，随着网络的不断发展，网络中的最短路径问题具有重要的理论意义和应用价值。当网络规模很大时,求解更加复杂,计算时间和所需的存储空间也大大的增加。本文讨论网络的最短路径算法及其现实问题，其中典型的最短路径算法是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 larg
5、e, 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 co
6、mplex, 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 so
7、urce 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 a
8、nd 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 efficie
11、ncy 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, app
12、ly 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 ex
13、tension 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 metho
14、d 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 t
15、wo 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 algorith
16、m 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, not suitable for large data calculations.KeywordsShortest path; Dijkstra algorithm; Floyd algorithm;
