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

作者：吴漫; 白明丽; 曾咏欣; 蒋峰; 利叶斌

来源：数学理论与应用, 2018, 38(Z2): 18-32.

• 割点
• 点割集
• Dijkstra算法
• 路由选择算法

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

• 单位
  湖南科技大学