最短路径快速算法 最短路径快速算法英語Shortest Path Faster Algorithm SPFA国际上一般认为是带有队列优化的BellmanFord 算法一般仅在中国大陆被称为SPFA是一个用于求解有向带权图单源最短路径的算法这一算法在随机的稀疏图上表现出色并且适用于带有负边权的图 然而SPFA在最坏情况的时间复杂度与 BellmanFord 算法相同因此在非负边权的图中使用堆优化的Dijkstra 算法效率可能优于SPFA SPFA算法首先在年由Edward F Moore英语Edward F Moore作为广度优先搜索的扩展发表相同算法在年由段凡丁重新发现