怎么修改网站首页logo,网页微博怎么下载视频,新闻软文广告,开发微信微商城图论 —— 最短路 —— Bellman-Ford 算法与 SPFA_通信网理论基础 分别使用bellman-ford算法和dijkstra算法的应用-CSDN博客
图解Bellman-Ford计算过程以及正确性证明 - 知乎 (zhihu.com)
语雀版本
1 概念
**适用场景#xff1a;**单源点#xff0c;可以有负边#xff0…图论 —— 最短路 —— 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 i0;in;i) dis[i]INF;dis[0]0;for(int i1;in-1;i)for(int j1;jm;j)//枚举所有边{int xu[j];//边j的起点int yv[j];//边j的终点if(dis[x]INF)//松弛dis[y]min(dis[y],dis[x]w[j]);}
}2.2 第n次变量——三角布不等式判断环
void Bellman_Ford()
{for(int i0;in;i) dis[i]INF;dis[0]0;for(int i1;in-1;i)for(int j1;jm;j)//枚举所有边{int xu[j];//边j的起点int yv[j];//边j的终点if(dis[x]INF)//松弛dis[y]min(dis[y],dis[x]w[j]);}for(int j1;jm;j)//枚举所有边{int xu[j];//边j的起点int yv[j];//边j的终点if(dis[y]dis[x]w[j])//cout有负权环;return;}
}3 SPFA-基于队列的优化
SPFAShortest Path Faster Algorithm。用队列来记录待遍历的点每次不遍历所有边只遍历和改点相邻的边。
3.1 实现 可以用双向队列把dis小的点放在队首提高遍历时更新的效率更快完成所有dis更新
struct Edge{int to,dis;
};
vectorEdge 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;dequeint 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);}}}}
}3.2 判断负环-判断每个点进队列的次数大于n
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;queueint 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;
}
