Bellman-Ford算法相关笔记
2025-01-11 20:42:40
发布于：广东
9阅读
0回复
0点赞
Bellman-Ford 算法
Bellman-Ford 算法可以在有负权值的图中寻找单源最短路径，可以判断图中是否有负权回路*
算法实现
对路径不断松弛，逐渐获取最短路径，直到有一次循环时没有松弛到一条边，算法结束。
Bellman-Ford 算法需要维护一个距离数组dis，其中*dis[i]*用来表示从起点到 i 号点的最短路径。
伪代码如下：
include<bits/stdc++.h>
using namespace std;
//初始化
int dis[s] = 0, dis[v] = 1e9 //v!=s, v取一个很大的值就行
//主函数
int main(){
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){ //枚举所有的边
//判断第 j 条边的终点的最短路径是否能被修改
}
}
//算法结束，dis数组变为以s点为起点到其他点的最短路径数组
return 0;
}
*负权回路，又称负权环，即图中的一个环的权值和为负数
这里空空如也
有帮助，赞一个