IT评测·应用市场-qidao123.com

标题: 8 Bellman Ford算法&SPFA [打印本页]

---

作者: 石小疯    时间: 2024-12-4 09:29
标题: 8 Bellman Ford算法&SPFA
图论 —— 最短路 —— Bellman-Ford 算法与 SPFA_通讯网理论基础 分别利用bellman-ford算法和dijkstra算法的应用-CSDN博客
图解Bellman-Ford计算过程以及正确性证明 - 知乎 (zhihu.com)
语雀版本
1 概念

**实用场景：**单源点，可以有负边，不能有负权环。
**dis(v)：**源点s到v的隔断。初始话dis(s)=0,别的为无穷大。
**n：**顶点数
**m：**边数
复杂度O(mn)：对边进行n-1次遍历。如果dis(v)>dis(u)+e(u,v)，则更新dis(v)=dis(u)+e(u,v)
**公道性：**基于这个方式，每次遍历最少有一个点的dis(v)是得到最优值。以是遍历n-1次就够了。
负权环：环的权值和为负。如果按上述的方式遍历，很有可能会导致某个点的dis值经过环之后变得更小。重复遍历后越来越小。
**判断负权环：**三角不等式。无负权环时，n-1次后所有dis都是最优。如果有，则会导致得不到最小dis。基于这一点，可以在n-1次后，再遍历一次，如果还存在dis(v)>dis(u)+e(u,v)，则有负权环。
2 实现

2.1 n-1次遍历

1. void Bellman_Ford()
2. {
3.     for(int i=0;i<n;i++)
4.         dis[i]=INF;
5.     dis[0]=0;
7.     for(int i=1;i<=n-1;i++)
8.         for(int j=1;j<=m;j++)//枚举所有边
9.         {
10.             int x=u[j];//边j的起点
11.             int y=v[j];//边j的终点
12.             if(dis[x]<INF)//松弛
13.                 dis[y]=min(dis[y],dis[x]+w[j]);
14.         }
15. }

复制代码

2.2 第n次变量——三角布不等式判断环

1. void Bellman_Ford()
2. {
3.     for(int i=0;i<n;i++)
4.         dis[i]=INF;
5.     dis[0]=0;
7.     for(int i=1;i<=n-1;i++)
8.         for(int j=1;j<=m;j++)//枚举所有边
9.         {
10.             int x=u[j];//边j的起点
11.             int y=v[j];//边j的终点
12.             if(dis[x]<INF)//松弛
13.                 dis[y]=min(dis[y],dis[x]+w[j]);
14.         }
15.     for(int j=1;j<=m;j++)//枚举所有边
16.         {
17.             int x=u[j];//边j的起点
18.             int y=v[j];//边j的终点
19.             if(dis[y]>dis[x]+w[j])//
20.                 cout<<"有负权环";
21.                 return;
22.         }
23. }

复制代码

3 SPFA-基于队列的优化

SPFA：Shortest Path Faster Algorithm。用队列来记录待遍历的点，每次不遍历所有边，只遍历和改点相邻的边。
3.1 实现

可以用双向队列，把dis小的点放在队首，提高遍历时更新的效率（更快完成所有dis更新）

1. struct Edge{
2.     int to,dis;
3. };
4. vector<Edge> edge[N];
5. bool vis[N];
6. int dis[N];
7. void SPFA(int s) {
8.     memset(dis, INF, sizeof(dis));
9.     memset(vis, false, sizeof(vis));
10.     vis[s] = true;
11.     dis[s] = 0;
12.    
13.     deque<int> Q;
14.     Q.push_back(s);
15.     while (!Q.empty()) {
16.         int x = Q.front();
17.         Q.pop_front();
18.         vis[x] = 0;
19.         for (int i = 0; i < edge[x].size(); i++) {
20.             int y = edge[x][i].to;
21.             if (dis[y] > dis[x] + edge[x][i].to) {
22.                 dis[y] = dis[x] + edge[x][i].to;
23.                 if (!vis[y]) {
24.                     vis[y] = true;
25.                     if (!Q.empty() && dis[y] < dis[Q.front()])//加入队首
26.                         Q.push_front(y);
27.                     else//加入队尾
28.                         Q.push_back(y);
29.                 }
30.             }
31.         }
32.     }
33. }

复制代码

3.2 判断负环-判断每个点进队列的次数（大于n）

1. struct Edge {
2.     int from, to;
3.     int dis;
4.     Edge() {}
5.     Edge(int from, int to, int dis) : from(from), to(to), dis(dis) {}
6. };
7. struct SPFA {
8.     int n, m;
9.     Edge edges[N]; //所有的边信息
10.     int head[N];   //每个节点邻接表的头
11.     int next[N];   //每个点的下一条边
12.     int pre[N];    //最短路中的上一条弧
13.     bool vis[N];
14.     int dis[N];
15.     int cnt[N]; //进队次数
17.     void init(int n) {
18.         this->n = n;
19.         this->m = 0;
20.         memset(head, -1, sizeof(head));
21.     }
23.     void AddEdge(int from, int to, int dist) {
24.         edges[m] = Edge(from, to, dist);
25.         next[m] = head[from];
26.         head[from] = m++;
27.     }
29.     bool negativeCycle(int s) { //判负环
30.         memset(vis, false, sizeof(vis));
31.         memset(cnt, 0, sizeof(cnt));
32.         memset(dis, INF, sizeof(dis));
33.         dis[s] = 0;
35.         queue<int> Q;
36.         Q.push(s);
38.         while (!Q.empty()) {
39.             int x = Q.front();
40.             Q.pop();
41.             vis[x] = false;
42.             for (int i = head[x]; i != -1; i = next[i]) {
43.                 Edge &e = edges[i];
44.                 if (dis[e.to] > dis[x] + e.dis) {
45.                     dis[e.to] = dis[x] + e.dis;
46.                     pre[e.to] = i;
47.                     if (!vis[e.to]) {
48.                         vis[e.to] = true;
49.                         Q.push(e.to);
50.                         if (++cnt[e.to] > n)
51.                             return true;
52.                     }
53.                 }
54.             }
55.         }
56.         return false;
57.     }
58. } spfa;
59. int main() {
60.     int n, m;
61.     while (scanf("%d%d", &n, &m) != EOF) {
62.         spfa.init(n);
63.         int S;
64.         scanf("%d", &S);
65.         for (int i = 1; i <= m; i++) {
66.             int x, y, dis;
67.             scanf("%d%d%d", &x, &y, &dis);
68.             //无向边添边两次
69.             spfa.AddEdge(x, y, dis);
70.             spfa.AddEdge(y, x, dis);
71.         }
72.         spfa.negativeCycle(S);
73.         for (int i = 1; i <= n; i++)
74.             printf("%d\n", spfa.dis[i]);
75.     }
76.     return 0;
77. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4