SPFA算法时间复杂度

SPFA（Shortest Path Faster Algorithm，最短路径更快算法），也称为Kleinberg's Shortest Paths First Algorithm，是一种用于求解图中单源最短路径的算法。它的基本思想是在广度优先搜索的基础上改进了松弛操作，同时处理负权边，避免了Bellman-Ford算法的O(|V| * |E|)时间复杂度。

SPFA的时间复杂度主要包括两部分：
1. 初始化阶段：遍历一次图，标记所有节点为已访问，并估计出每个顶点到起点的距离。这部分的时间复杂度约为O(V + E)，其中V是顶点数，E是边数。
2. 主循环阶段：每次从一个等待队列中选择一个未确定最短路径的节点，进行松弛操作。对于每一环路检查（即沿着一条边到达的另一个节点已经通过其他路径得到了更新），它需要遍历整个邻接列表，这一步的时间复杂度大致是O(E)。

由于可能会有无限次的环路检查，理论上来说，如果存在负权环，SPFA将运行至无穷，但实际上通常会在有限步内找到结果，因为负权环会使得某些节点的估计距离不断减小直至达到最小值。因此，如果图中不存在负权环，SPFA在一个可行时间内（通常是O((V+E) * log V)）就能找到最短路径。