关于最短路径的SPFA快速算法

被引：56

作者：

段凡丁

机构：

[1] 西南交通大学计算中心

来源：

西南交通大学学报 | 1994年 / 02期

关键词：

有向图；最短路径；算法；时间复杂性;

D O I：

暂无

中图分类号：

O224 [最优化的数学理论];

学科分类号：

摘要：

本文提出了关于最短路径问题的一种新的快速算法─—ＳＰＦＡ（ＳｈｏｒｔｅｓｔＰａｔｈＦａｓｔｅｒＡｌｇｏｒｉｔｈｍ）算法．ＳＰＦＡ算法采用动态优化逼近的方法，用邻接表作为有向图的存储结构，用了一个先进先出的队列Ｑｕｅｕｅ来作为待优化点的存储池。算法的时间复杂性为Ｏ（ｅ），在绝大多数情况下，图的边数ｅ和顶点数ｎ的关系是ｅ＜ｎ￣２，因此，ＳＰＦＡ算法比经典的Ｄｉｊｋｓｔｒａ算法在时间复杂性方面更优越。

引用

页码：207 / 212

页数：6