SPFA算法—单源最短路径问题

概念

SPFA算法(Shortest Path Faster Algorithm)是一种解决单源最短路径问题的算法,用邻接表或邻接矩阵来存储图,主要用于处理带有负权边的图。其基本思路是通过动态逼近法对图进行松弛操作,不断更新结点的最短路径估计值,直至收敛到最优解。

思路与理解

  1. 初始化: 将所有结点的最短路径估计值初始化为无穷大,然后将起始结点的最短路径估计值设为0。将起始结点放入队列中。

  2. 动态逼近法: 通过不断从队列中取出结点进行松弛操作,更新结点的最短路径估计值。具体步骤如下:

    • 从队列中取出一个结点u。
    • 遍历u的所有邻接结点v,对v进行松弛操作,即通过u更新v的最短路径估计值。
    • 如果v的最短路径估计值有所调整,且v不在当前队列中,则将v放入队尾。
  3. 判断负环: 在执行过程中,检测是否存在负环。两种方法:

    • 在算法开始前,通过拓扑排序判断图是否有环,一般不采用,因为可能浪费时间。
    • 统计每个结点进入队列的次数,如果某个结点的入队次数超过图的顶点数N,则存在负环。
  4. 终止条件: 当队列为空时,算法终止。

例子

一个简单的图示例,其中有5个结点(城市):A、B、C、D、E。边上的数字表示两城市间的距离

A --2--> B
|       /
1     3 
| /     
C --4--> D
      
  5   
    
    E

假设我们从城市A开始,初始化距离数组为无穷大,将A的最短路径估计值设为0。然后将A加入队列

第一轮

  • 从队列中取出A。
  • 更新B和C的最短路径估计值。
  • 将B和C加入队列
  A(0)
  |
  2  
  |         1
  B(2) -- C(1)
  |     
  3  
  |    
  D(∞) 
  |   
  4  
  | 
  E(∞)

第二轮

  • 从队列中取出B
  • 更新D的最短路径估计值
  • 将D加入队列
  A(0)
  |
2 |     1
  B(2) -- C(1)
  |  
  3  
  |   
  D(∞) 
  |   
  4  
  | 
  E(∞)

第三轮

  • 从队列中取出C
  • 更新D的最短路径估计值
  • 将D加入队列
  A(0)
  |
  2 
  |          1
  B(2) -- C(1)
  |      
  3  
  |    
  D(5) 
  |   
  4  
  | 
  E(∞)

第四轮

  • 从队列中取出D
  • 更新E的最短路径估计值
  • 将E加入队列
  A(0)
  |
2 |     1
  B(2) -- C(1)
  |      
  3  
  |    
  D(5) 
  |  
  4  
  | 
  E(9)

第五轮

  • 从队列中取出E
  • 没有相邻结点,结束

具体应用

spfa求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m

接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围
1≤n,m≤105
图中涉及边长绝对值均不超过 10000。

输入样例

3 3
1 2 5
2 3 -3
1 3 4

输出样例

2

代码与思路

  1. 通过add方法建立邻接表,表示图中的有向边信息。
  2. 使用SPFA算法求解单源最短路径。算法维护一个队列,不断松弛每个结点的邻接边,直到没有可以松弛的边为止。
  3. 最终得到起点到终点的最短路径长度,如果为0x3f3f3f3f,表示不可达,输出"impossible";否则输出最短路径长度
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n, m, idx, N = 100010;
    static int[] ne = new int[N], e = new int[N], w = new int[N], h = new int[N], dis = new int[N];
    static boolean[] state = new boolean[N];

    // 添加一条有向边,起点是a,终点是b,权重是c
    public static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx ++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);

        // 读取图的边信息,建立邻接表
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            add(x, y, z);
        }

        // 使用SPFA算法求解单源最短路径
        int t = spfa();

        // 输出结果
        if (t == 0x3f3f3f3f) {
            System.out.println("impossible");
        } else {
            System.out.println(dis[n]);
        }
    }

    // SPFA算法,返回从起点到终点的最短路径长度
    private static int spfa() {
        Arrays.fill(dis, 0x3f3f3f3f);
        dis[1] = 0;

        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        state[1] = true;

        while (!q.isEmpty()) {
            int t = q.poll();
            state[t] = false;

            // 遍历t的所有邻接点
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];

                // 如果通过t到达j的路径更短,则更新最短路径估计值
                if (dis[j] > dis[t] + w[i]) {
                    dis[j] = dis[t] + w[i];

                    // 如果j不在队列中,将j加入队列
                    if (!state[j]) {
                        q.offer(j);
                        state[j] = true;
                    }
                }
            }
        }
        return dis[n];
    }
}

spfa判断负环

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

如果图中存在负权回路,则输出 Yes,否则输出 No

数据范围

1≤n≤2000
1≤m≤10000
图中涉及边长绝对值均不超过 10000。

输入样例:

3 3
1 2 -1
2 3 4
3 1 -4

输出样例:

Yes

代码与思路

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n, m, idx, N = 100010;
    static int[] ne = new int[N], e = new int[N], w = new int[N],
            h = new int[N], dis = new int[N], cnt = new int[N];
    static boolean[] state = new boolean[N];

    // 添加一条有向边,起点是a,终点是b,权重是c
    public static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        w[idx] = c;
        h[a] = idx++;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h, -1);

        // 读取图的边信息,建立邻接表
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            add(x, y, z);
        }

        // 判断图中是否存在负环
        if (!spfa()) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }

    // SPFA算法,判断图中是否存在负环
    private static boolean spfa() {
        Queue<Integer> q = new LinkedList<>();

        // 初始化队列,将所有点加入队列
        for (int i = 1; i <= n; i++) {
            state[i] = true;
            q.offer(i);
        }

        // 遍历队列
        while (!q.isEmpty()) {
            int t = q.poll();
            state[t] = false;

            // 遍历t的所有邻接点
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];

                // 如果通过t到达j的路径更短,则更新最短路径估计值
                if (dis[j] > dis[t] + w[i]) {
                    dis[j] = dis[t] + w[i];
                    cnt[j] = cnt[t] + 1;

                    // 如果j不在队列中,将j加入队列
                    if (cnt[j] >= n) return true;
                    if (!state[j]) {
                        state[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
        return false;
    }
}