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

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

作　　者：吴漫 白明丽 曾咏欣 蒋峰 利叶斌 Wu Man;Bai Mingli;Zeng Yongxin;Jiang Feng;Li Yebin(Hunan University of Science and Technology,Xiangtan 411100,China)

机构地区：[1]湖南科技大学数学与计算科学学院

出　　处：《数学理论与应用》2018年第3期18-32,共15页Mathematical Theory and Applications

基　　金：湖南省大学生研究性学习和创新性试验计划项目（201810534042）资助

摘　　要：本文通过介绍图论中的重要内容——割点与点割集的概念,将寻找割点与点割集的算法,与经典的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.

关 键 词：割点 点割集 DIJKSTRA算法 路由选择算法 

分 类 号：O157.5[理学—数学]