图论中的最短路径快速算法（SPFA） 题目描述 给定一个带权有向图，图中可能包含负权边，但不存在负权环（即环上各边权重之和为负）。要求计算从指定源点出发到所有其他顶点的最短路径长度。若图中存在负权环，算法应能检测到这一情况。SPFA（Shortest Path Faster Algorithm）是对Bellman-Ford算法的优化，通过动态选择待松弛的顶点来减少不必要的计算。 解题过程 问题分析 负权边使得Dijkstra算法无法直接应用（贪心选择可能失效）。 Bellman-Ford算法通过对所有边进行\(V-1\)轮松弛操作保证最短路径的收敛，但每轮遍历所有边效率较低（时间复杂度\(O(VE)\)）。 SPFA的核心思想：仅当某个顶点的最短路径估计值被更新时，才将其加入队列以待后续松弛，避免无效操作。 算法准备 数据结构： dist[] ：记录源点到各顶点的当前最短距离估计，初始时源点设为0，其余为无穷大。 queue ：存储待松弛的顶点（通常使用FIFO队列或双端队列）。 inQueue[] ：标记顶点是否在队列中，避免重复入队。 count[] ：记录顶点入队次数，用于检测负权环（若某顶点入队次数超过\(V-1\)次，说明存在负权环）。 松弛操作：对于边\((u, v)\)，若 dist[u] + weight(u, v) < dist[v] ，则更新 dist[v] 并触发入队操作。 算法步骤 初始化 ： 将源点加入队列，标记 inQueue[source]=true ， dist[source]=0 。 迭代处理队列 ： 从队列中取出一个顶点\(u\)，标记 inQueue[u]=false 。 遍历\(u\)的所有出边\((u, v)\)，执行松弛操作： 若 dist[v] 被更新且\(v\)不在队列中，则将\(v\)入队并标记 inQueue[v]=true ，同时增加 count[v] 。 若 count[v] > V-1 ，立即终止并报告负权环。 终止条件 ： 队列为空时，算法正常结束；若检测到负权环则提前终止。 实例演示 考虑一个包含顶点{A, B, C, D}的图，边权为：A→B(2), A→C(3), B→D(-1), C→D(1)，源点为A。 初始：队列=[ A], dist[ A ]=0, 其他为∞。 处理A：更新B(2)、C(3)，队列变为[ B, C ]。 处理B：更新D(2+(-1)=1)，队列变为[ C, D ]。 处理C：尝试更新D（3+1=4 > 当前1），无变化，队列剩[ D ]。 处理D：无出边，队列空。最终dist[ D ]=1。 复杂度与注意事项 时间复杂度：平均\(O(E)\)，最坏\(O(VE)\)（与Bellman-Ford相同，但实际效率通常更高）。 负权环检测需严格监控入队次数，避免无限循环。 若图结构稀疏或权重变化较小，SPFA优势明显；但对于刻意构造的数据可能退化成Bellman-Ford。