关于最短路径的SPFA快速算法 |
| |
引用本文: | 段凡丁.关于最短路径的SPFA快速算法[J].西南交通大学学报,1994,29(2):207-212. |
| |
作者姓名: | 段凡丁 |
| |
作者单位: | 西南交通大学计算中心 |
| |
摘 要: | 本文提出了关于最短路径问题的一种新的快速算法-SPFA算法。SPFA算法采用动态优化逼近的方法,用邻接表作为有向图的存储结构,用了一个先进先出的队列Queue来作为待优化点的存储池。算法的时间复杂性为O(e),在绝大多数情况下,图的边数e和顶点n的关系是e<n^2,因此,SPFA算法比经典的Dijkstra逄法在时间复杂方面更优越。
|
关 键 词: | 最短路径 SPFA算法 运筹学 |
本文献已被 CNKI 维普 等数据库收录! |
|