基于矩阵运算的最短路优化算法

发布时间：2018-02-28 14:36

本文关键词： 最短路算法矩阵消去算法矩阵自定义运算稀疏网络 K短路径算法　出处：《南京邮电大学》2017年硕士论文　论文类型：学位论文

【摘要】：最短路问题作为图论和复杂网络中经典问题,现在在日常生活中,也出现在许许多多方面,比如通信网络,交通网络,旅行商问题中。然而用来求解最短路径的问题的解法也是数见不鲜,其中最典型的要数Dijkstra算法、Ford算法和Floyd算法。然而Dijkstra算法只可求出2个指定节点间的最短距离,Ford算法就只可以求出指定始发点的最短路径,而Floyd算法计算过程相当繁琐。最重要的是,这些算法都是仅仅能解决两节点间的1条最短路。而在实际生活中,我们有时还会因为一些给定的前提条件需要求出两点间次短、渐次短路径。根据以上的不足,本文提出了基于矩阵运算的最短路径优化算法,主要内容如下:1.针对Ford算法进行改进,提出了一种固定始发点的矩阵消去算法,通过寻找从一个固定始发点到其他顶点的路径,其中包括不经过别的顶点,经过一个顶点、经过两个顶点等等逐步迭代,找出从固有始发点到其它的顶点间的最短路。2.给出基于矩阵自定义运算的改良算法。本算法是凭借一种自定义的矩阵运算来求出一个代表每2个节点间距离的路权修正矩阵,然后用路权修正矩阵和原本的距离矩阵来比较,选择2个矩阵中相应较小的元素,组成当前的最短路权矩阵,接着,通过有限次迭代,从而获得各个顶点间的最短路径。并用MATLAB实现,将这种算法运用到随机的大规模复杂网络中去,从运行时间折线图上看出这种算法在节点数到达较大的数量后,算法速度显著提高,在稀疏网络中,该算法的效率特别高,这表明该算法的有效性。最终,经过真实的应用场景表明了这种算法的实用性。3.通过对距离矩阵和路径矩阵的迭代、替换操作,不断从一个节点出发寻找其后继节点,同时通过比较路径长短得到两点间最短路径、次短路径、渐次短路径,并用一个实际例子对该算法的实用价值加以说明。最后,在一个大型网络的实际例子中,通过MATLAB对该算法进行仿真,求得指定顶点间最短、次短、渐次短路径说明该算法能够在复杂大规模随机网络中得到应用。
[Abstract]:As a classical problem in graph theory and complex network, the shortest path problem appears in many aspects of daily life, such as communication network, transportation network, In the traveling Salesman problem. However, the solution to solve the shortest path problem is not uncommon. The most typical of them are the Dijkstra algorithm and the Floyd algorithm. However, the Dijkstra algorithm can only find the shortest path between the two designated nodes, and only the shortest path of the specified starting point can be obtained by the Dijkstra algorithm. And the Floyd algorithm is rather cumbersome. Most importantly, these algorithms can only solve the shortest path between two nodes. And in real life, we sometimes need to find two points short because of some given preconditions. According to the deficiency above, this paper proposes the shortest path optimization algorithm based on matrix operation. The main contents are as follows: 1. Aiming at the improvement of Ford algorithm, a matrix elimination algorithm with fixed starting point is proposed. By looking for a path from a fixed starting point to another vertex, which includes a step by step iteration through a vertex, a vertex, two vertices, etc. Find out the shortest path from the original point to the other vertices. 2. Give an improved algorithm based on the matrix custom operation. This algorithm is based on a custom matrix operation to find a path weight correction matrix representing the distance between each two nodes. Then the path weight correction matrix is compared with the original distance matrix, and the corresponding smaller elements in the two matrices are selected to form the current shortest path weight matrix. The shortest path between each vertex is obtained, and the algorithm is implemented by MATLAB. The algorithm is applied to random large-scale complex network. From the running time broken line graph, it can be seen that this algorithm has a large number of node points. The efficiency of the algorithm is especially high in sparse networks, which shows the effectiveness of the algorithm. Finally, the practicability of the algorithm is demonstrated by a real application scenario. Finally, by iterating the distance matrix and the path matrix, the algorithm is proved to be practical. Replace operation, constantly from a node to find its successor nodes, and by comparing the length of the path between the shortest path, the second short path, the gradual short path, A practical example is given to illustrate the practical value of the algorithm. Finally, in a practical example of a large network, the algorithm is simulated by MATLAB to obtain the shortest and the second shorter between specified vertices. The gradual short path shows that the algorithm can be applied to complex large scale random networks.
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】