马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
图论 —— 最短路 —— 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次遍历
- void Bellman_Ford()
- {
- for(int i=0;i<n;i++)
- dis[i]=INF;
- dis[0]=0;
-
- for(int i=1;i<=n-1;i++)
- for(int j=1;j<=m;j++)//枚举所有边
- {
- int x=u[j];//边j的起点
- int y=v[j];//边j的终点
- if(dis[x]<INF)//松弛
- dis[y]=min(dis[y],dis[x]+w[j]);
- }
- }
- void Bellman_Ford()
- {
- for(int i=0;i<n;i++)
- dis[i]=INF;
- dis[0]=0;
-
- for(int i=1;i<=n-1;i++)
- for(int j=1;j<=m;j++)//枚举所有边
- {
- int x=u[j];//边j的起点
- int y=v[j];//边j的终点
- if(dis[x]<INF)//松弛
- dis[y]=min(dis[y],dis[x]+w[j]);
- }
- for(int j=1;j<=m;j++)//枚举所有边
- {
- int x=u[j];//边j的起点
- int y=v[j];//边j的终点
- if(dis[y]>dis[x]+w[j])//
- cout<<"有负权环";
- return;
- }
- }
SPFA：Shortest Path Faster Algorithm。用队列来记录待遍历的点，每次不遍历所有边，只遍历和改点相邻的边。
3.1 实现
可以用双向队列，把dis小的点放在队首，提高遍历时更新的效率（更快完成所有dis更新）- struct Edge{
- int to,dis;
- };
- vector<Edge> edge[N];
- bool vis[N];
- int dis[N];
- void SPFA(int s) {
- memset(dis, INF, sizeof(dis));
- memset(vis, false, sizeof(vis));
- vis[s] = true;
- dis[s] = 0;
-
- deque<int> Q;
- Q.push_back(s);
- while (!Q.empty()) {
- int x = Q.front();
- Q.pop_front();
- vis[x] = 0;
- for (int i = 0; i < edge[x].size(); i++) {
- int y = edge[x][i].to;
- if (dis[y] > dis[x] + edge[x][i].to) {
- dis[y] = dis[x] + edge[x][i].to;
- if (!vis[y]) {
- vis[y] = true;
- if (!Q.empty() && dis[y] < dis[Q.front()])//加入队首
- Q.push_front(y);
- else//加入队尾
- Q.push_back(y);
- }
- }
- }
- }
- }
- struct Edge {
- int from, to;
- int dis;
- Edge() {}
- Edge(int from, int to, int dis) : from(from), to(to), dis(dis) {}
- };
- struct SPFA {
- int n, m;
- Edge edges[N]; //所有的边信息
- int head[N]; //每个节点邻接表的头
- int next[N]; //每个点的下一条边
- int pre[N]; //最短路中的上一条弧
- bool vis[N];
- int dis[N];
- int cnt[N]; //进队次数
-
- void init(int n) {
- this->n = n;
- this->m = 0;
- memset(head, -1, sizeof(head));
- }
-
- void AddEdge(int from, int to, int dist) {
- edges[m] = Edge(from, to, dist);
- next[m] = head[from];
- head[from] = m++;
- }
-
- bool negativeCycle(int s) { //判负环
- memset(vis, false, sizeof(vis));
- memset(cnt, 0, sizeof(cnt));
- memset(dis, INF, sizeof(dis));
- dis[s] = 0;
-
- queue<int> Q;
- Q.push(s);
-
- while (!Q.empty()) {
- int x = Q.front();
- Q.pop();
- vis[x] = false;
- for (int i = head[x]; i != -1; i = next[i]) {
- Edge &e = edges[i];
- if (dis[e.to] > dis[x] + e.dis) {
- dis[e.to] = dis[x] + e.dis;
- pre[e.to] = i;
- if (!vis[e.to]) {
- vis[e.to] = true;
- Q.push(e.to);
- if (++cnt[e.to] > n)
- return true;
- }
- }
- }
- }
- return false;
- }
- } spfa;
- int main() {
- int n, m;
- while (scanf("%d%d", &n, &m) != EOF) {
- spfa.init(n);
- int S;
- scanf("%d", &S);
- for (int i = 1; i <= m; i++) {
- int x, y, dis;
- scanf("%d%d%d", &x, &y, &dis);
- //无向边添边两次
- spfa.AddEdge(x, y, dis);
- spfa.AddEdge(y, x, dis);
- }
- spfa.negativeCycle(S);
- for (int i = 1; i <= n; i++)
- printf("%d\n", spfa.dis[i]);
- }
- return 0;
- }
|
