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