借鉴：https://blog.csdn.net/hjd_love_zzt/article/details/26739593
关于贝尔曼福特算法,假设有n个顶点，我们只需要遍历n-1轮就可以了，因为在一个含n个顶点的图中，任意两点之间的最短路径最多含有n-1条边, 什么原理，我就不讲了，网上大牛博客很多，我在这里上一点干货：
1.最原始的贝尔曼福特算法，时间复杂度为O（NM）：
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#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],check,flag;
//读入顶点个数和边的条数
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++)
{check=0;//标记数组dis在本轮松弛中是否会发生更新
for(int i=1; i<=m; i++)
if(dis[u[i]]+w[i]<dis[v[i]])
{
dis[v[i]]=dis[u[i]]+w[i];
check=1;//数组dis发生更新，改变check的值
}
//松弛完毕后检测dis是否有更新
if(check==0)break;//如果没有更新，提前退出循环
}
//检测负权回路并输出结果
flag=0;
for(int i=1; i<=m; i++)
if(dis[u[i]]+w[i]<dis[v[i]])
flag=1;
if(flag==1)
printf("此图含有负权回路\n");
else
{
for(int i=1; i<=n; i++)
printf("%d ",dis[i]);
}
}
适用范围：给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点
算法思想：我们用数组d记录每个结点的最短路径估计值，用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止
SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，
并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中
一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本
身被改进，于是再次用来改进其它的点，这样反复迭代下去。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
思路上与狄克斯特拉算法(Dijkstra algorithm)最大的不同是每次都是从源点s重新出发进行"松弛"更新操作，而Dijkstra则是从源点出发向外扩逐个处理相邻的节点，不会去重复处理节点，这边也可以看出Dijkstra效率相对更高点。
贝尔曼福特算法的队列优化，时间复杂度为O（N）：
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define maxnum 3010
#define inf 0x3f3f3f
using namespace std;
int dis[maxnum],n,m,u[maxnum],v[maxnum],w[maxnum];
int first[maxnum],next[maxnum],vis[maxnum];
int main()
{
queue<int>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;
}
//1号顶点入队
vis[1]=1;
q.push(1);
while(!q.empty())
{
int k=first[q.front()];
while(k!=-1)//扫描当前顶点所有的边
{
if(dis[u[k]]+w[k]<dis[v[k]])//判断是否松弛成功
{
dis[v[k]]=dis[u[k]]+w[k];//更新顶点1到顶点v[k]的路程
if(vis[v[k]]==0)//判断一个顶点是否在队列中，为0表示不在队列，加入队列
{
q.push(v[k]);
vis[v[k]]=1;//同时标记顶点v[k]已经入队
}
}
k=next[k];
}
vis[q.front()]=0;
q.pop();
}
//输出结果
for(int i=1; i<=n; i++)
printf("%d ",dis[i]);
return 0;
}
小结
1.广度优先算法BFS主要适用于无权重向图重搜索出源点到终点的步骤最少的路径，当方向图存在权重时，不再适用
2.狄克斯特拉算法Dijkstra主要用于有权重的方向图中搜索出最短路径，但不适合于有负权重的情况.对于环图，个人感觉和BFS一样，标志好已处理的节点避免进入死循环，可以支持
3.贝尔曼-福特算法Bellman–Ford主要用于存在负权重的方向图中(没有负权重也可以用，但是效率比Dijkstra低很多)，搜索出源点到各个节点的最短路径
4.Bellman–Ford可以判断出图是否存在负环路，但存在负环路的情况下不支持计算出各个节点的最短路径。只需要在结束(节点数目-1)次遍历后，再执行一次遍历，若还可以更新数据则说明存在负环路
5.当人为限制了遍历次数后，对于负环路也可以计算出，但似乎没啥实际意义
网友评论