SPFA + 链式前向星建图【附Java模板】-Toy模板网

这篇具有很好参考价值的文章主要介绍了SPFA + 链式前向星建图【附Java模板】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

SPFA + 链式前向星建图【附Java模板】

SPFA算法是什么？它能解决什么样的问题？

🌷 仰望天空，妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅，敬请批评指正！🐥

🦩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;
    }

}