基于BFS算法的有阻断路径的最短路径算法研究

Research on the shortest path algorithm with blocking path based on BFS algorithm

针对大规模网络中所有节点的全源最短路径的计算需求,文中基于广度优先遍历(BFS)思想,在计算过程中设置存储队列,引入阻断路径,限制后续图节点的扩展范围,完成了图的减枝,大幅度降低最短路径计算的时间复杂。经测试,文中所设计的算法相较于传统Dijkstra算法在高、中、低规模的数据集上均可降低50%以上的运算时间;相较于BFS算法,可以降低20%以上的运算时间。

In this paper,the shortest path algorithm is designed for computing the shortest path of all nodes in large-scale networks.Based on the idea of breadth first traversal(BFS),this method sets up storage queues,introduces blocking paths,limits the extension range of subsequent graph nodes,completes the reduction of graph branches,and greatly reduces the time complexity of shortest path calculation.Compared with the traditional Dijkstra algorithm,the proposed algorithm can reduce more than 50%of the operation time on high,medium and low-scale data sets,and can reduce more than 20%of the operation time compared with the BFS algorithm.