● SPFA 算法1SPFA 算法即最短路径快速算法是基于 Bellman-Ford 算法优化而来的单源最短路径算法适用于带负权边、无负权环的有向图或无向图在算法竞赛中应用广泛。2SPFA 算法借助队列对 Bellman-Ford 算法进行优化仅将松弛成功、距离被更新的节点入队只处理存在更新潜力的节点减少冗余运算。3在 CSP/NOIP 等算法竞赛中遇到负权图优先选用 SPFA 算法求最短路径若图无负权边推荐堆优化 Dijkstra求最短路径。● SPFA 算法核心流程1初始化距离数组 dist[]。设 dist[s] 代表起点 s 到各点的最短距离先将起点距离置为 0其余节点初始化为无穷大。同时创建队列保存被松弛更新成功的待处理节点并借助 st[] 数组标记节点入队状态以此避免节点重复入队减少冗余计算。2循环取出队首节点 u遍历 u 的全部邻边 u→v。若满足松弛条件 dist[v]dist[u]w(u,v)则更新 dist[v]如果本次松弛成功且节点 v 不在队列中就将 v 入队。持续迭代直到队列为空。3队列为空算法结束。若任意节点入队次数≥节点总数 n说明图中存在负环。● SPFA 算法经典实例AcWing 851spfa求最短路 → https://blog.csdn.net/hnjzsyjyj/article/details/138425339AcWing 852spfa判断负环 → https://blog.csdn.net/hnjzsyjyj/article/details/138470784洛谷 P3385[模板] 负环 → https://blog.csdn.net/hnjzsyjyj/article/details/166784851洛谷 P3371[模板] 单源最短路径弱化版 → https://blog.csdn.net/hnjzsyjyj/article/details/166788143