【图论】——最短路问题_带有负权重的无向图,不满足三角不等式

【图论】——最短路问题

概述

• 设 n 为点数，m 为边数
• 按照源点的个数可以分为：

1. 单源最短路问题（从图中某一个点到其他点）
   再按是否有负权边分为：

• 所有边权为整正数：
  Dijkstra（朴素）——>$O(n^2)$——> 用于稠密图
  Dijkstra（堆优化）——> $O(m\log n)$——> 用于稀疏图
• 存在边权为负
  Bellman-Ford——>$O(m\ast n)$
  SPFA——> $O(m)$

2. 多源汇最短路问题（图中多个起点到其他点）
   Floyd——> $O(n^3)$

单源最短路问题

• 对于一个有向图，如果所有点都满足三角不等式，则 dis 数组就是所求的最短距离：
  $$dis[y]\le dis[t]+z$$

不存在负权边

Dijkstra（朴素）——>$O(n^2)$——> 用于稠密图

• 思路：
  

• 代码：

int g[M][M];// 邻接矩阵
int dis[M];// 存储 start 到每点的距离
bool st[M];// 存储当前点是否被确定了距离（是否被拿去更新过所有点）
int n, m;
void save_1()// 邻接矩阵的读入
{memset(g 0x3f, sizeof g);
    int a, b;
    scanf("%d%d%d", &a, &b, &c);
    g[a][b] = min(g[a][b], c);}
int dijkstra(int start, int end)
{
    // 初始化为正无穷
    memset(dis, 0x3f, sizeof dis);
    dis[start] = 0;
    for (int i = 0; i < n - 1; i++) {
        // 寻找当前距离 start 最小的点
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        // 现在 t 就是没有被确定过的距离 start 最近的点
        if (t == end)// 如果距离最近的点是 end，找到答案提前结束
            return dis[end];
        for (int j = 1; j <= n; j++)// 用 t 来更新到其他所有点的距离
            dis[j] = min(dis[j], dis[t] + g[t][j]);
        st[t] = true;// 将 t 距离确定
    }
    return dis[end];
}
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

Dijkstra（堆优化）——> $O(m\log n)$——> 用于稀疏图

• 思路
  

typedef pair<int,int> PII;// 第二个 int 用来存下标，第一个 int 用来存从 start 到当前点的距离，方便排序
int h[N], e[N], ne[N], w[N], idx;// 用邻接表来存储边
int dis[N];// 存储 start 到每点的距离
bool st[N];// 存储当前点是否被确定了距离（是否被拿去更新过所有点）
memset(h, -1, sizeof - 1);// 表头初始化为空
void add(int a, int b, int c)// 邻接表的读入
{e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx++] = c;
}
int dijkstra(int start, int end)
{
    // 初始化距离为正无穷
    memset(dis, 0x3f, sizeof dis);
    dis[start] = 0;
    // 使用堆来优化每次寻找最近点的操作（朴素版遍历寻找 t 的过程）
    priority_queue<PII, vector<PII>, greater<PII>> heap;// 小根堆
    heap.push(PII(0, 1));// 将起点入堆
    while (heap.size()) {
        // 取出最近的点
        auto t = heap.top();
        heap.pop()；
        int idx = t.second;// 获得下标（朴素版的 t）
        if (idx == end)// 如果最近的点是 end，提前结束
            return dis[end];
        if (st[idx])// 如果这个点的距离已经被确定过了，跳过
            continue;
        else
            st[idx] = true;// 标记被确定
        for (int i = h[idx]; i != -1; i = ne[i]) {// 遍历这个点所有的邻边，并用这个点来更新
            int j = e[i];
            if (dis[j] > dis[idx] + w[i]) {
                // 如果不满足三角不等式，更新答案，同时入堆
                dis[j] = dis[idx] + w[i];
                heap.push(PII(dis[j], j));}
        }
    }
    return dis[end];
}
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

存在负权边

Bellman-Ford——>$O(m\ast n)$

• 用结构体存储每条边即可
• 可以用来计算限制最大步数的最短路
• 思路：
  

int dis[M], bkup[M];// 创建 dis 和 dis 的备份，备份的用处在下文
int n, m, k;//n 为点数，m 为边数，k 为最大合法步数
struct Edge// 用于存储每条边的信息
{int a, b, w;} edges[N];
// 读入每条边：
int a,b,w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};

int bellman_ford(int start,int end)
{
    // 首先初始化为正无穷
    memset(dis,0x3f,sizeof dis);/
    dis[start] = 0;
    for (int i = 0; i < k; i++) {memccpy(bkup, dis, sizeof dis);
        /* 为什么要备份：
            在运用三角不等式更新 dis 时，由于边的枚举不是按序的，可能会将需要用到的上一点的 dis 更新，导致在更新当前点时用到的上一点的 dis 出错，
            因此在循环枚举每条边的时候要先将 dis 备份
        */
        // 枚举所有边
        for (int j = 0; j < m;j++){int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;
            dis[b] = min(dis[b], bkup[a] + w);// 若用 dis[a]+w, 由于枚举不是按序，如果之前有存在可以更新 dis[a] 的边会导致当前的 dis[b] 出错，很有可能 b 与之前更新过 a 的点没有连通。
        }
    }
    return dis[end];
}
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

SPFA——> $O(m)$（队列优化的 Bellman-Ford 算法）

• Bellman 是每次遍历所有的边，在遍历过程中其实真正对答案起到作用的是当某点不满足三角不等式时的更新，换言之，dis[a] 变小是因为他的前一个点 dis[b] 变小造成的
• 因此，类似于 BFS 的方式，用队列来优化这个过程可以将复杂度优化到线性
• 思路：
  

int h[N], e[N], ne[N], w[N], idx;// 邻接表的存储
int dis[N];// 存储 start 到其他点的距离
bool st[N];// 判断当前点是否入队
int n, m;//n 为点数，m 为边数
queue<int> q;// 队列
void add(int a, int b, int c)
{e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx++] = c;
}
memset(h,-1,sizeof h);// 表头初始化为空
int spfa(int start, int end)
{
    // 初始化为正无穷
    memset(dis, 0x3f, sizeof dis);
    dis[start] = 0;
    // 将起点入队
    q.push(start);
    st[start] = true;
    while (q.size()) {auto t = q.front()；// 取出队头
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {// 更新队头的所有邻边
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) {// 如果不满足三角不等式，更新该点
                dis[j] = dis[t] + w[i];
                if (st[j])// 如果已经在队中跳过
                    continue;
                q.push(j);// 否则入队
                st[j] = true;
            }
        }
    }
    return dis[end];// 当队中所有元素都更新完，返回 dis（不能提前返回，因为不知道仍在队中的元素是否会把当前答案更新）
}
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

SPFA 判断负环

• 记录一下从 start 到每个点所经过的边数，由抽屉原理可知，如果 cnt≥n 则证明一定存在 n+1 个点，但是只有 n 个点，证明有边经过了多次，只有存在负环才会让 dis 无休止的小下去
• 思路：
  

int e[M], ne[M], h[M], w[M], idx;//邻接表存储
int dis[N], cnt[N];//cnt记录每个点被经过的次数
bool st[N];//判断是否在队中
int n, m;//n为点数，m为边数
queue<int> q;
void add(int a, int b, int c)//邻接表读入
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx++] = c;
}
bool judge_spfa()//spfa判断负环
{
    memset(dis, 0x3f, sizeof dis);//初始化
    for (int i = 1; i <= n; i++) {//将每个点都入队当作起点
        dis[i] = 0;
        q.push(i);
        st[i] = true;
    }
    while (q.size()) {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dis[j] > dis[t] + w[i]) {//如果不满足三角不等式
                dis[j] = dis[t] + w[i];//更新距离
                cnt[j] = cnt[t] + 1;//更新经过该点最多次数
                if (cnt[j] >= n)//如果cnt≥n则证明至少有n+1个点，矛盾，有负环
                    return true;
                if (st[t])//已经在队中就不用加了
                    continue;
                q.push(j);//否则入队
                st[j] = true;
            }
        }
    }
    return false;
}
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

多源汇最短路问题

Floyd——> $O(n^3)$

• 算法本质为 DP，状态表示为：$dp(k,i,j)$
• 表示：经过若干个序号不超过 $k$ 的节点，从 $i$ 走向 $j$ 的最短长度
• 可以将其化为两个子集合：

1. 经过编号不超过 $k-1$ 的节点从 $i$ 走向 $j$ 的最短长度
2. 经过编号不超过 $k-1$ 的节点从 $i$ 走向 $k$，再由 $k$ 走向 $j$ 的最短长度

• 转移方程：
  d p (   k   ,   i   ,   j   ) = m i n   {   d p (   k − 1   ,   i   ,   j   )   ,   d p (   k − 1   ,   i   ,   k   )   +   d p (   k − 1   ,   k   ,   j   ) } dp(\ k\ ,\ i\ ,\ j\ ) = min\ \{\ dp(\ k-1\ ,\ i\ ,\ j\ )\ ,\ dp(\ k-1\ ,\ i\ ,\ k\ )\ +\ dp(\ k-1\ ,\ k\ ,\ j\ )\} dp( k , i , j )=min { dp( k−1 , i , j ) , dp( k−1 , i , k ) + dp( k−1 , k , j )}
• 状态压缩，由于每次更新只会用到 $k-1$ 的值，因此可以用滚动数组压缩，去掉 $k$ 层。
  d p (   i   ,   j   ) = m i n   {   d p (   i   ,   j   )   ,   d p (   i   ,   k   )   +   d p (   k   ,   j   ) } dp(\ i\ ,\ j\ ) = min\ \{\ dp(\ i\ ,\ j\ )\ ,\ dp(\ i\ ,\ k\ )\ +\ dp(\ k\ ,\ j\ )\} dp( i , j )=min { dp( i , j ) , dp( i , k ) + dp( k , j )}
• 代码

int dis[N][N];// 邻接矩阵
int n, m;//n 为点数，m 为边数
memset(dis, 0x3f, sizeof dis);// 初始化为正无穷
void floyd()
{
    // 初始化为原地距离为 0
    for (int i = 1; i <= n;i++)
        dis[i][i] = 0;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13