关于贝尔曼福特算法,假设有n个顶点，我们只需要遍历n-1轮就可以了，因为在一个含n个顶点的图中，任意两点之间的最短路径最多含有n-1条边, 什么原理，我就不讲了，网上大牛博客很多，我在这里上一点干货：
1.最原始的贝尔曼福特算法，时间复杂度为O（NM）：
再次学习
外层进行n-1次循环，内层进行m次循环，内层每进行一次循环，至少找出来一条边能走通，而图有n个点，所以进行n-1就够了。 经过我数据的实验，它只能检查出来负权边，而不能避免负权边（就是每进行一次循环距离就会减少，我也不知道怎么描述QAQ）。
#include#include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define maxnum 3010 #define inf 0x3f3f3f using namespace std; int main() { int dis[10],n,m,u[10],v[10],w[10]; //读入顶点个数和边的条数 scanf("%d%d",&n,&m); //读入边 for(int i=1; i<=m; i++) scanf("%d%d%d",&u[i],&v[i],&w[i]); //初始化dis数组 for(int i=1; i<=n; i++) dis[i]=inf; dis[1]=0; //贝尔曼-福特算法(Bellman-Ford)的核心语句 for(int k=1; k<=n-1; k++) for(int i=1; i<=m; i++) if(dis[u[i]]+w[i]
这个算法还可以用来检测一个图是否含有负权回路，如果进行了n-1轮松弛操作后仍然存在：
if(dis[u[i]]+w[i]
如果这种情况持续存在，那么这个图一定含有负权回路。
有时候在n-1轮松弛之前就已经算出了最短路，这时候我们可以判断一下来进行优化：#include#include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define maxnum 3010 #define inf 0x3f3f3f using namespace std;//开四个数组 int dis[10],n,m,u[10],v[10],w[10],check,flag;int main() { //读入顶点个数和边的条数 scanf("%d%d",&n,&m); //第一步，读入边 for(int i=1; i<=m; i++) scanf("%d%d%d",&u[i],&v[i],&w[i]); //第二步，初始化dis数组 for(int i=1; i<=n; i++) dis[i]=inf; dis[1]=0; //第三步，贝尔曼-福特算法(Bellman-Ford)的核心语句 for(int k=1; k<=n-1; k++) { for(int i=1; i<=m; i++) if(dis[u[i]]+w[i]
2.贝尔曼福特算法的队列优化，时间复杂度为O（N）：
#include#include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define maxnum 3010 #define inf 0x3f3f3f using namespace std; //开7个数组int dis[maxnum],n,m,u[maxnum],v[maxnum],w[maxnum]; int first[maxnum],next[maxnum],vis[maxnum]; int main() { queue q; //读入顶点个数和边的条数 scanf("%d%d",&n,&m); //首先三个初始化 //第一步，初始化dis数组 for(int i=1; i<=n; i++) dis[i]=inf; dis[1]=0; //第二步，初始化vis for(int i=1; i<=n; i++) vis[i]=0; //第三步，初始化first的下标为-1，表示1~n号顶点暂时都没有边 for(int i=1; i<=n; i++) first[i]=-1; //第四步，读入边并建立邻接表 for(int i=1; i<=m; i++) { scanf("%d%d%d",&u[i],&v[i],&w[i]); next[i]=first[u[i]]; first[u[i]]=i; } //第五步，起始顶点入队 vis[1]=1; q.push(1); while(!q.empty()) { //第六步，下一个点开始 int k=first[q.front()]; while(k!=-1)//扫描当前顶点所有的边 { if(dis[u[k]]+w[k]
对于上面的代码，给出两组样例：
输入： 5 5 2 3 2 1 2 -3 1 5 5 4 5 2 3 4 3 输出： 0 -3 -1 2 4 输入： 5 7 1 2 2 1 5 10 2 3 3 2 5 7 3 4 4 4 5 5 5 3 6 输出： 0 2 5 9 9