一种基于路径阻断的求解最短路径算法

摘要：

全源最短路径的求解是计算机科学、交通工程、地理信息系统等学科中的一个研究热点.随着网络规模不断增大,求解全源最短路径的时间复杂度急剧上升,这制约了复杂网络相关研究与应用的快速发展,因此最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题.本文在BFS的基础上,引入路径阻断策略,利用已求得的单源最短路径节点的结果,加速全源最短路径的求解.实验结果表明该方法对大规模网络全源最短路径实现了加速计算.

关键词：复杂网络、全源最短路径、广度优先遍历、路径阻断

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61602026

在线出版日期：2018-01-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：6-11