关于最短路径的SPFA快速算法
-
摘要: 本文提出了关于最短路径问题的一种新的快速算法─—SPFA(ShortestPathFasterAlgorithm)算法.SPFA算法采用动态优化逼近的方法,用邻接表作为有向图的存储结构,用了一个先进先出的队列Queue来作为待优化点的存储池。算法的时间复杂性为O(e),在绝大多数情况下,图的边数e和顶点数n的关系是e<n ̄2,因此,SPFA算法比经典的Dijkstra算法在时间复杂性方面更优越。
点击查看大图
计量
- 文章访问数: 1486
- HTML全文浏览量: 61
- PDF下载量: 117
- 被引次数: 0