基于点割集的最短路径算法的改进与应用

Improvement and Application of Shortest Path Algorithm Based on Point Cut Set

本文通过介绍图论中的重要内容——割点与点割集的概念,将寻找割点与点割集的算法,与经典的Dijkstra算法结合,形成改进的并行算法并予以实现与应用,为寻找无向图的最短路径提供了理论依据,并用其改进了路由协议OSPF中的路由选择算法,降低了算法的时间复杂度.

By introducing the concept of cut point and point cut set,which are the important part of graph theory,this paper combines the algorithm of finding cut point and point cut set with the classical Dijkstra algorithm to form an improved parallel algorithm.The application of the improved parallel algorithm is also given.It provides a theoretical basis for finding the shortest path of undirected graph,and improves the routing algorithm in the routing protocol OSPF,which reduces the time complexity of the algorithm.