首页 程序设计 图与树 最短路算法

# Spfa 求最短路

# 背景

给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，边权可能为负数
请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 impossible
数据保证不存在负权回路

# 数据范围

1≤n,m≤1051 \le n,m \le 10^5

# 思路

利用邻接表存图，队列操作
如果当前到 j(e[i]) 点的步数小于遍历时，先去 d[t] 点再去 j(e[i]) 点的步数，则更新 d[j] 的值

  • 如果此时， j(e[i]) 还恰好不在队列中，则推入队列
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    int e[N], ne[N], h[N], w[N], idx = 0;
    int d[N];
    bool st[N];
    int n, m, a, b, c;

    void add(int a, int b, int c) {
        e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
    }

    void spfa() {
        memset(d, 0x3f, sizeof d), d[1] = 0, st[1] = true;
        queue<int> q;
        q.push(1);

        while (q.size()) {
            int t = q.front();
            q.pop();

            st[t] = false;

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];

                if (d[j] > d[t] + w[i]) {
                    d[j] = d[t] + w[i];

                    if (!st[j])
                        q.push(j), st[j] = 1;
                }
            }
        }
    }

    void solve () {
        memset(h, -1, sizeof h);

        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            cin >> a >> b >> c, add(a, b, c);

        spfa();

        if (d[n] == 0x3f3f3f3f)
            cout << "impossible\n";
        else
            cout << d[n] << "\n";
    }

# Spfa 判负环

# 背景

给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，边权可能为负数
请你判断图中是否存在负权回路

# 数据范围

  • 1≤n≤20001 \le n \le 2000
  • 1≤m≤100001 \le m \le 10000

# 思路

本质还是 SpfaSpfa 算法，建立一个 cntcnt 数组， cnt[i] 表示到有多少条边能到第 ii 个点
由抽屉原理可知，如果存在 ii 满足 cnt[i] > n ，则必存在负环

注意：与 SpfaSpfa 不同的是，此处不关注路径长度，而是图中是否存在负环，初始时应该将所有点都 pushpush 进队列

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int e[N], ne[N], h[N], w[N], idx = 0;
int d[N], cnt[N];
bool st[N];
int n, m, a, b, c;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        q.push(i), st[i] = 1;

    while (q.size()) {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];

            if (d[j] > d[t] + w[i]) {
                cnt[j] = cnt[t] + 1;
                
                if (cnt[j] > n)
                    return 1;

                d[j] = d[t] + w[i];

                if (!st[j])
                    q.push(j), st[j] = 1;
            }
        }
    }

    return 0;
}

void solve () {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a >> b >> c, add(a, b, c);

    cout << (spfa() ? "Yes" : "No") << endl;
}