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

A Faster Algorithm for Shortest-Ptath──SPFA

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

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.