🦩SPFA算法的概念
🍐SPFA算法（Shortest Path Faster Algorithm）是一种单源最短路径算法，用于求解带权有向图中某个源点到其他所有点的最短路径。它是对Bellman-Ford算法的优化，通过使用队列来避免重复松弛操作，从而提高了算法的效率。SPFA算法的时间复杂度为O(kE)，其中k是一个常数，通常情况下k小于2，因此SPFA算法的时间复杂度可以认为是O(E)。
🐸SPFA和Dijkstra的区别
🍋 同样是单源最短路径算法，它和Dijkstra有什么区别？
🍒 SPFA（Shortest Path Faster Algorithm）和Dijkstra算法都是用于解决单源最短路径问题的算法，但它们有以下几个区别：
🪁1.时间复杂度：Dijkstra算法的时间复杂度为O(ElogV)，其中E为边数，V为顶点数；而SPFA算法的时间复杂度为O(kE)，其中k为常数，一般情况下k小于2，但在最坏情况下，k可以达到V。
🪁2.实现方式：Dijkstra算法使用堆优化的贪心策略，每次选择当前距离最小的未访问节点进行松弛操作；而SPFA算法使用队列实现，每次选择当前距离最小的未访问节点进行松弛操作。
🪁3.稳定性：Dijkstra算法对于边权值为负的图无法处理，而SPFA算法可以处理负权边，但是在存在负环的情况下，SPFA算法会进入死循环。
🪁综上，Dijkstra算法适用于边权值为正的图，时间复杂度较低；而SPFA算法适用于边权值为负的图，但时间复杂度较高，且存在负环的情况下会出现问题。
🐳SPFA算法的解题步骤
SPFA算法的解题步骤如下：
🦕1. 初始化：将起点的距离设为0，其余点的距离设为无穷大，将起点加入队列。
🦕2. 进行松弛操作：从队列中取出一个点，遍历其所有邻居节点，如果通过该点可以使邻居节点的距离更短，则更新邻居节点的距离，并将其加入队列中。
🦕3. 重复步骤2，直到队列为空。
🦕4. 如果终点的距离被更新过，则说明存在从起点到终点的路径，输出最短路径长度。
🦕5. 如果终点的距离没有被更新过，则说明不存在从起点到终点的路径。
需要注意的是，为了避免负权边导致的死循环，需要在每次更新距离时判断是否存在负权环，如果存在则说明最短路径不存在。
🦕模板题：“随机数据下的最短路问题”
题目描述
给定 N 个点和 M 条单向道路，每条道路都连接着两个点，每个点都有自己编号，分别为 1 ~ N 。
问你从 S 点出发，到达每个点的最短路径为多少。
输入描述
输入第一行包含三个正整数 N,M,S。
第 2 到 M + 1 行每行包含三个正整数 u,v,w，表示 u→v 之间存在一条距离为 w 的路。
1≤N≤5×10^3 , 1≤M≤5×10^4 , 1≤ui,vi≤N , 0≤wi≤10^9
本题数据随机生成。
输出描述
输出仅一行，共 N 个数，分别表示从编号 S 到编号为 1 ~ N 点的最短距离，两两之间用空格隔开。（如果无法到达则输出 -1）
输入输出样例 示例 1
输入
3 3 1
1 2 1
1 3 5
2 3 2
输出
0 1 3
运行限制
最大运行时间：1s 最大运行内存: 128M
🦕【模板Code（含判断负环）】
import java.io.*; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; public class Main { static int N = (int) (5e3 + 10), M = (int) (5e4 + 10); static int[] head = new int[M], ends = new int[M], next = new int[M], weights = new int[M];//链式前向星 static boolean[] st = new boolean[N];//表示某个点是否在队列里面，注意并非是否访问过 static int n, m, s, total; static long[] dist = new long[N]; static long[] cnt = new long[N];//判断是否负环回路; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static void add(int start, int end, int weight) { ends[total] = end; weights[total] = weight; next[total] = head[start]; head[start] = total++; } public static void main(String[] args) throws IOException { n = nextInt(); m = nextInt(); s = nextInt(); Arrays.fill(head, -1); for (int i = 0; i < m; i++) add(nextInt(), nextInt(), nextInt()); if (SPFA()) System.out.println("存在负环回路"); else System.out.println("无负环回路"); for (int i = 1; i <= n; i++) { if (dist[i] == Long.MAX_VALUE) out.print("-1" + " "); else out.print(dist[i] + " "); } out.flush(); } static boolean SPFA() { Deque<Integer> queue = new ArrayDeque<>(); Arrays.fill(dist, Long.MAX_VALUE); dist[s] = 0;//初始点 queue.offer(s); st[s] = true; while (!queue.isEmpty()) { int hh = queue.poll(); st[hh] = false; for (int i = head[hh]; i != -1; i = next[i]) { int j = ends[i]; if (dist[j] > dist[hh] + weights[i]) { dist[j] = dist[hh] + weights[i]; cnt[j] = cnt[hh] + 1; if (cnt[j] >= n) return true;//判断是否负环回路; if (!st[j]) {// 当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率 queue.offer(j); st[j] = true; } } } } return false; } static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } }
🦕【解题Code_AC】
import java.io.*; import java.util.*; public class Main { static int N = (int) (5e3 + 10), M = (int) (5e4 + 10); static int[] head = new int[M], ends = new int[M], next = new int[M], weights = new int[M]; static boolean[] st = new boolean[N]; static int n, m, s, total; static long[] dist = new long[N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static void add(int start, int end, int weight) { ends[total] = end; weights[total] = weight; next[total] = head[start]; head[start] = total++; } public static void main(String[] args) throws IOException { n = nextInt(); m = nextInt(); s = nextInt(); Arrays.fill(head, -1); for (int i = 0; i < m; i++) add(nextInt(), nextInt(), nextInt()); SPFA(); for (int i = 1; i <= n; i++) { if (dist[i] == Long.MAX_VALUE) out.print("-1" + " "); else out.print(dist[i] + " "); } out.flush(); } static void SPFA() { Deque<Integer> queue = new ArrayDeque<>(); Arrays.fill(dist, Long.MAX_VALUE); dist[s] = 0L; queue.offer(s); st[s] = true; while (!queue.isEmpty()) { int hh = queue.poll(); st[hh] = false; for (int i = head[hh]; i != -1; i = next[i]) { int j = ends[i]; if (dist[j] > dist[hh] + weights[i]) { dist[j] = dist[hh] + weights[i]; if (!st[j]) { queue.offer(j); st[j] = true; } } } } } static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } }
🐳结语
🐬初学一门技术时，总有些许的疑惑，别怕，它们是我们学习路上的点点繁星，帮助我们不断成长。
🐟文章粗浅，希望对大家有帮助！
