最短路_解题技巧

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

使用

SPFA与Dijkstra的选择

如果dp存在后效性，即状态转移存在环形，就需要使用单源最短路算法进行解决。

Dijkstra由于使用贪心策略，只会出队一次；SPFA则会出队若干次，直到所有条件收敛。

判断Dijkstra还是SPFA的常用办法，自己创造一个环，根据节点定义走一遍，看看初始节点是否会被重复更新。

举个例子，有1、2、3三个点，1 -> 2，2 -> 3，3 -> 1三条边构成一个环

如果定义d[x]代表到达x的最短路径开销，设d[1] = 5

  • 如果边权不为负，不管怎样点1都不会被重复更新，设三条边边权都为0，d[1] = 5，就算转一圈开销也还是5，不会被更新。
  • 如果边权为负，设三条边边权均为-1，转一圈后d[1] = 5 - 3 = 2，显然只出一次队列是不够的，这也是为什么负权边要用SPFA而不是Dijkstra

再举一个例子，定义d[x]代表到达x的最小值，设d[1] = 5

设节点2的值为2，节点3的值为1，转一圈回到节点1后d[1] = 1，也说明Dijkstra是不够用的。

Bellman-Ford的核心

根据最短路的定义，最短路的边数不会超过n - 1，否则存在负环，那么每个节点最多扩展n - 1次。

Bellman-Ford就是暴力地遍历全图所有边n - 1次，SPFA只是使用队列稍微规避了一些不必要的扩展，是可以构造数据退化为暴力的。

练习题

模板

Dijkstra（邻接矩阵暴力）

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
#include <bits/stdc++.h>
using namespace std;
int n, m, a[505][505], d[505];
bool v[505];

int main() {
  cin >> n >> m;
  memset(a, 0x3f, sizeof(a));
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    a[x][y] = min(a[x][y], z);
  }
  for (int i = 1; i <= n; i++) a[i][i] = 0;
  memset(d, 0x3f, sizeof(d));
  d[1] = 0;
  for (int cnt = 1; cnt <= n; cnt++) {
    int min_val = 1 << 30, x;
    for (int i = 1; i <= n; i++)
      if (!v[i] && d[i] < min_val) min_val = d[i], x = i;
    v[x] = true;
    for (int y = 1; y <= n; y++) d[y] = min(d[y], d[x] + a[x][y]);
  }
  if (d[n] == 0x3f3f3f3f)
    puts("-1");
  else
    cout << d[n] << endl;
}

Dijkstra（堆优化）

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
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 150005, MAX_M = 150005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, d[MAX_N];
bool v[MAX_N];
// pair<-dist[x], x>
priority_queue<pair<int, int>> q;

// 插入一条从x到y长度z的有向边
void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x]; // 在head[x]这条链的开头插入新点
    head[x] = tot;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = true;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push(make_pair(-d[y], y));
            }
        }
    }
    if (d[n] == 0x7f7f7f7f) puts("-1");
    else cout << d[n] << endl;
}

Bellman-Ford

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
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 150005, MAX_M = 150005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, d[MAX_N];

// 插入一条从x到y长度z的有向边
void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x]; // 在head[x]这条链的开头插入新点
    head[x] = tot;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;
    for (int cnt = 1; cnt <= n - 1; cnt++) {
        bool flag = false;
        for (int x = 1; x <= n; x++) {
            for (int i = head[x]; i; i = nxt[i]) {
                int y = ver[i], z = edge[i];
                if (d[y] > d[x] + z) {
                    d[y] = d[x] + z;
                    flag = true;
                }
            }
        }
        if (!flag) break;
    }
    if (d[n] == 0x7f7f7f7f) puts("impossible");
    else cout << d[n] << endl;
}

SPFA

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
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 150005, MAX_M = 150005;
int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
int n, m, d[MAX_N];
bool v[MAX_N]; // 点是否在队列中
queue<int> q;

// 插入一条从x到y长度z的有向边
void add(int x, int y, int z) {
    tot++;
    ver[tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x]; // 在head[x]这条链的开头插入新点
    head[x] = tot;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;
    q.push(1); v[1] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop(); v[x] = false;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (!v[y]) { q.push(y); v[y] = true; }
            }
        }
    }
    if (d[n] == 0x7f7f7f7f) puts("impossible");
    else cout << d[n] << endl;
}