526互联

搜索与图论2.3-Bellman-Ford算法

发布时间 2023-10-28 20:39:34作者: Cocoicobird

一、简述

\(Bellman-Ford\) 算法是一种可以求解存在负权边的单源最短路问题的算法。

二、Bellman-Ford算法

  • 对于所有边权大于等于 \(0\) 的图，任意两个顶点之间的最短路，显然不会经过重复的顶点或者边。也就是说任意一条最短路经过的顶点数不会超过 \(n\)，边不会超过 \(n-1\) 条。
  • 对于有权边为负的图，有可能存在负环，此时途径负环的最短路没有意义（注意：不是说存在负环的图中就不存在最短路）。

\(Bellman-Ford\) 算法的核心思想是松弛操作，即对于边 \((u,v)\)，用 \(dist(u)\) 和 \(l(u,v)\) 的和尝试更新 \(dist(v)\)：\(dist(v)=min(dist(v),dist(u)+l(u,v))\)。\(Bellman-Ford\) 所做的就是不断尝试对图上每一条边进行松弛操作。进行多次迭代，每进行一次迭代，就对图上所有的边都尝试进行一次松弛操作，当一次迭代中没有点的 \(dist\) 发生改变时，算法停止。
在最短路存在的情况下，由于一次迭代会使最短路的边数至少加一，而 \(S\) 到每个顶点的最短路经过的边数最多为 \(n-1\)，因此整个算法最多进行 \(n-1\) 轮迭代，每一轮迭代的复杂度为 \(O(m)\)，所以总的复杂度为 \(O(nm)\)。
当从 \(S\) 出发能够达到一个负环时，就会经过 \(n\) 轮以上的迭代。
如何判断负环？

  • 枚举所有顶点进行 \(Bellman-Ford\)，时间复杂度 \(O(n^2m)\)
  • 假设存在一个超级源点，该点到所有顶点的距离为 \(0\)，则 \(dist(u)=0\)，进行 \(Bellman-Ford\)，如果迭代 \(n\) 轮仍然会更新，则存在负环

模板如下

struct Edge {
	int x, y, v;
} edge[M + 1];
int n, m, dist[N], pre[N];

int bellman_ford(int s, int t) {
	memset(dist, 127, sizeof dist);
	dist[s] = 0;
	for ( ; ; ) {
		bool ok = false;
		for (int i = 1; i <= m; i++) {
			int x = edge[i].x, y = edge[i].y, v = edge[i].v;
			if (dist[x] < 1 << 30)
				if (dist[x] + v < dist[y]) {
					dist[y] = dist[x] + v;
					pre[y] = x;
					ok = true;
				}
		}
		if (!ok)
			break;
	}
	return dist[t];
}

三、Bellman-Ford算法的优化方式

  • 队列优化（\(SPFA\)）：在每一次迭代时，只有在上一次迭代中被更新距离的点，才有可能去更新其它节点。因此在每一次迭代时，将更新过距离的顶点加入到一个队列（如果顶点已在队列中则不加），在下一次迭代时只需要遍历队列中的顶点连出去的边即可。
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

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

int spfa() {
    memset(dist, 127, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = 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(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if(!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

容易被卡成 \(O(nm)\) 复杂度

\(SPFA\) 也可用于求解是否存在负环的问题，假设存在超级源点到所有顶点距离为 \(0\)，\(dist(u)=0\)，所有顶点入队，设置数组 \(cnt\) 记录到当前顶点的边数，假设存在边 \(i\) 到 \(j\)，如果更新，则 \(cnt(j)=cnt(i)+1\)，如果存在 \(cnt≥n\) 则存在负环。

四、Bellman-Ford算法的应用

1.[AcWing853.有边数限制的最短路]

题目描述

给定一个 \(n\) 个点 \(m\) 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 \(1\) 号点到 \(n\) 号点的最多经过 \(k\) 条边的最短距离，如果无法从 \(1\) 号点走到 \(n\) 号点，输出 impossible。
注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 \(n,m,k\)。
接下来 \(m\) 行，每行包含三个整数 \(x,y,z\)，表示存在一条从点 \(x\) 到点 \(y\) 的有向边，边长为 \(z\)。
点的编号为 \(1∼n\)。

输出格式

输出一个整数，表示从 \(1\) 号点到 \(n\) 号点的最多经过 \(k\) 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。

数据范围

\(1≤n,k≤500\)，
\(1≤m≤10000\)，
\(1≤x,y≤n\)，任意边长的绝对值不超过 \(10000\)。

输入样例
3 3 1
1 2 1
2 3 1
1 3 3
输出样例
3
解题思路

基本思路是利用 \(Bellman-Ford\) 算法，因为算法的松弛过程在最短路存在的情况下最多进行 \(n-1\) 次，因此我们可以利用这个特点来进行思考：每次迭代都看作边数 \(+1\)，那么最多进行 \(k\) 次迭代，此外，在每次迭代中要避免串联现象，比如存在 \(1 \rightarrow 2,2 \rightarrow 3,1 \rightarrow 3\)，而最多经过 \(1\) 条边，那么最短路只能是 \(1 \rightarrow 3\) 的边权，但是由于串联，本次迭代中会使得 \(2 \rightarrow 3\) 更新，正确做法是使用上次的结果，因此这里使用了一个 \(last\) 数组用于记录上次迭代的结果用于此次更新。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010;

int n, m, k;
int dist[N], last[N];
struct Edge {
    int a, b, w;    
} edges[M];

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], last[a] + w);
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int  i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2)
        puts("impossible");
    else
        printf("%d\n", dist[n]);
    return 0;
}

2.[AcWing852.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
解题思路

见本文的第二部分。

C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

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

bool spfa() {
    //memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        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 (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                
                if (!st[j]) {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if (spfa())
        puts("Yes");
    else 
        puts("No");
    return 0;
}