图论：单源最短路径问题-SPFA

发表于 2022-07-15 更新于 2022-07-18 分类于 acwing算法基础课笔记 Artalk： loading...

Shortest Path Faster Algorithm, SPFA

队列优化后的Bellman-Ford算法

SPFA

最短路径快速算法，Shortest Path Faster Algorithm

$n$ 代表图的顶点数量， $m$ 代表图的边的数量

平均时间复杂度 $\Omicron(m)$

最坏时间复杂度 $\Omicron(nm)$

关于SPFA的最坏时间复杂度，参考
Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
如何看待 SPFA 算法已死这种说法？

对BF进行优化

观察Bellman Ford算法流程

算法主要是两重循环

每一次迭代，都是遍历所有的边，进行松弛操作

只有当一个边的起点 $a$ 更新过时，终点 $b$ 的 $dist$ 才可能会变小

基于此，可以用队列进行优化，类似BFS的代码形式

每一次，对所有以队首元素为起点的边的终点执行松弛操作，只将更新过的终点加入队列中，直至队列为空

算法流程

伪代码

// 赋初值
for each vertex v in V
     dist[v] = INF
dist[orig] = 0

Q.offer(orig)
while Q is not empty
    u = Q.poll()
    for each edge (a, b) in E(G)
        if dist[a] + w(a, b) < dist[b] // 松弛操作
            dist[b] = dist[a] + w(a, b)
            if b is not in Q
                Q.offer(b)

Tips

1.

SPFA算法无需备份dist数组，因为SPFA求解最短路时，不考虑边数限制

2.

队列里都是由起点更新到的顶点，不存在bellman-ford算法中未更新的点同样被边更新的情况

代码实现

核心代码

st数组的含义，true:代表队列中存在该顶点，可以避免重复更新

int[] spfa() {
    Arrays.fill(dist, INF);
    dist[1] = 0;
    Queue<Integer> q = new LinkedList<>();
    q.offer(1);
    st[1] = true;
    while (!q.isEmpty()) {
        int cur = q.poll();
        
        st[cur] = false; // st数组，true:代表队列中有该顶点
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[cur] + w[i]) {
                dist[j] = dist[cur] + w[i];
                if (!st[j]) {
                    q.offer(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist;
}

java完整代码

acwing 51. spfa求最短路

import java.util.*;
import java.io.*;

class Main{
    static final int N = 100010;
    static final int M = 100010;
    static final int INF = 0x3f3f3f3f;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    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) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]); m = Integer.parseInt(str[1]);
        int a, b, c;
        Arrays.fill(h, -1);
        for (int i = 0; i < m; ++i) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]); b = Integer.parseInt(str[1]); c = Integer.parseInt(str[2]);
            add(a, b, c);
        }
        spfa();
        cin.close();
    }
    static void spfa() {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        st[1] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            st[cur] = false;
            
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[cur] + w[i]) {
                    dist[j] = dist[cur] + w[i];
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        if (dist[n] == INF) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}

优化技巧

可以通过优化队列质量来提升整体性能

@Wiki

距离小者优先(Small Label First, SLF)，由Bertsekas在Networks, 第23期, 1993, P703-P709中最先提出

松弛操作时，将更新的顶点和队列首部元素比较，如果 $\text{dist[b] < dist[q.peekFirst]}$ ，则将顶点 $b$ 放入队首 $\text{q.offerFirst(b)}$

spfa判断负环

应用SPFA算法判断图中是否存在负权回路

原理

同Bellman Ford算法，都是利用「抽屉原理」判断负环

假如图有 $n$ 个顶点，若存在一个最短路径长度为 $n$ 的话，此路径上有 $n + 1$ 个点，一定有两个点是同一个顶点，即存在环路

实现逻辑

引入一个新数组 $count[]$ 来记录路径的长度（边数）

发生更新

$dist[b] = dist[a] + weight<a\to b>$

$count[b] = count[a] + 1$

一旦 $count[b] \ge n$ ，证明存在环路

代码

核心代码

注意，负权回路不一定是从源点出发的

因此一开始，将所有点放入队列中

boolean spfa() {
    Arrays.fill(dist, INF);
    dist[1] = 0;
    Queue<Integer> q = new LinkedList<>();
    // 将所有点放入队列
    for (int i = 1; i <= n; ++i) {
        st[i] = true;
        q.offer(i);
    }
    while (!q.isEmpty()) {
        int cur = q.poll();
        
        st[cur] = false; // st数组，true:代表队列中有该顶点
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[cur] + w[i]) {
                dist[j] = dist[cur] + w[i];
                cnt[j] = cnt[cur] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.offer(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

java完整代码

acwing 852. spfa判断负环

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

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

import java.util.*;
import java.io.*;

class Main {
    static final int N = 2010;
    static final int M = 10010;
    static final int INF = 0x3f3f3f3f;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] cnt = new int[N];
    static int n, m;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));

    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) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        int a, b, c;
        Arrays.fill(h, -1);
        for (int i = 0; i < m; ++i) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]);
            b = Integer.parseInt(str[1]);
            c = Integer.parseInt(str[2]);
            add(a, b, c);
        }
        boolean res = spfa();
        if (res) System.out.println("Yes");
        else System.out.println("No");
        cin.close();
    }

    static boolean spfa() {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        // 
        for (int i = 1; i <= n; ++i) {
            st[i] = true;
            q.offer(i);
        }
        while (!q.isEmpty()) {
            int cur = q.poll();

            st[cur] = false; // st数组，true:代表队列中有该顶点
            for (int i = h[cur]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[cur] + w[i]) {
                    dist[j] = dist[cur] + w[i];
                    cnt[j] = cnt[cur] + 1;
                    if (cnt[j] >= n) return true;
                    if (!st[j]) {
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return false;
    }
}

参考资料

📔博文图谱

提及本博文的链接

图论：最短路径问题-Dijkstra