|
|||||
|
|
| 基于BFS算法的有阻断路径的最短路径算法研究 | |
| 作者单位： | ;1.广东理工学院信息技术学院;2.广东交通职业技术学院 |
| 摘 要： | 针对大规模网络中所有节点的全源最短路径的计算需求,文中基于广度优先遍历(BFS)思想,在计算过程中设置存储队列,引入阻断路径,限制后续图节点的扩展范围,完成了图的减枝,大幅度降低最短路径计算的时间复杂。经测试,文中所设计的算法相较于传统Dijkstra算法在高、中、低规模的数据集上均可降低50%以上的运算时间;相较于BFS算法,可以降低20%以上的运算时间。 |
| 关 键 词： | 最短路径 广度优先遍历 Dijkstra 图论 |
Research on the shortest path algorithm with blocking path based on BFS algorithm |
|
| Abstract: | |
| Keywords: | |