摘要
本文提出了关于最短路径问题的一种新的快速算法─—ＳＰＦＡ（ＳｈｏｒｔｅｓｔＰａｔｈＦａｓｔｅｒＡｌｇｏｒｉｔｈｍ）算法．ＳＰＦＡ算法采用动态优化逼近的方法，用邻接表作为有向图的存储结构，用了一个先进先出的队列Ｑｕｅｕｅ来作为待优化点的存储池。算法的时间复杂性为Ｏ（ｅ），在绝大多数情况下，图的边数ｅ和顶点数ｎ的关系是ｅ＜ｎ￣２，因此，ＳＰＦＡ算法比经典的Ｄｉｊｋｓｔｒａ算法在时间复杂性方面更优越。
This paper offers a new fast algorithm for shortest-path prolem─ SPFA. The data structrue of SPFA algorithm uses adjacency list and a FIFO queue,Applying dynamic optimal approach , the time complexity of SPFA algorithm is O(e),it is better than Dijkstra’s typical algorithm when e《n￣2. No particular limitation conditions are needed.So the SPFA algorithm can be adapted for all directed graphs.
出处
《西南交通大学学报》
EI
CSCD
北大核心
1994年第2期207-212,共6页
Journal of Southwest Jiaotong University
关键词
最短路径
SPFA算法
运筹学
directed graph
shortest-path
algorithm
time complexity
