图论中的最短路径快速算法（SPFA） 题目描述 给定一个带权有向图（可能存在负权边，但无负权环），以及一个源点 \( s \)，要求计算从 \( s \) 到图中所有其他顶点的最短路径长度。若图中存在负权环，则算法应能检测到这一情况。 解题思路 SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 算法的优化版本，通过动态更新可能改善最短路径的顶点来减少冗余计算。其核心思想是： 仅当某个顶点的最短距离被更新时，才将其加入队列进行后续松弛操作。 通过记录顶点的入队次数来检测负权环。 步骤详解 初始化 创建一个数组 dist[] ，初始化 dist[s] = 0 ，其余顶点为无穷大（表示尚未到达）。 创建一个队列 Q ，将源点 s 入队，并标记 s 已入队。 创建一个数组 count[] 记录每个顶点的入队次数，初始化为 0。 队列处理 当队列非空时，取出队首顶点 u ，并将其标记为已出队。 遍历 u 的所有出边 (u, v, w) （即从 u 到 v 的边权为 w ）： 松弛操作 ：若 dist[v] > dist[u] + w ，则更新 dist[v] = dist[u] + w 。 若 v 不在队列中，则将 v 入队，并增加 v 的入队次数 count[v]++ 。 负权环检测 ：若任何顶点的 count[v] 超过图中顶点总数 \( n \)，说明存在负权环，算法终止。 终止条件 队列为空时，算法正常结束， dist[] 即为最短路径结果。 若检测到负权环，则输出提示信息。 示例说明 考虑一个简单图：顶点集 \(\{A, B, C\}\)，边集 \(A \to B\)（权值 2）、\(B \to C\)（权值 -1）、\(C \to A\)（权值 -2\)。 初始化： dist[A]=0 ，其他为 ∞，队列初始为 \([ A ]\)。 处理 A ：更新 B 的距离为 2， B 入队。 处理 B ：更新 C 的距离为 1， C 入队。 处理 C ：更新 A 的距离为 -1， A 再次入队。 重复过程中，若某个顶点的入队次数超过 3，则检测到负权环（因为边 \(C \to A\) 的权值 -2 与 \(A \to B \to C\) 形成负循环）。 关键点 SPFA 在平均情况下时间复杂度为 \(O(m)\)（\(m\) 为边数），最坏情况下退化为 \(O(nm)\)。 负权环检测依赖于顶点入队次数，超过 \(n\) 次即存在环。 适用于稀疏图且含负权边的场景，但需注意稳定性问题。