BF求图的最短路径的时间复杂度是O(MN)，这样的时间复杂度并不比迪杰斯特拉算法好，但是BF算法支持图中存在负权的情况，但图中不能存在负圈，因为如果存在负圈，最短路是不存在的，因此BF算法的另一个重要应用是判负圈（如果松弛了N-1次后，还能松弛，就说明存在负圈）
简单写法（没有判断是否存在负圈。判断负圈只要在最后判断能否继续进行松弛即可）
#include<iostream>
using namespace std;
;
<<;
int d[maxn],w[maxn],f[maxn],t[maxn];
int main()
{
int N,M;
cin>>N>>M;
;i<M;i++){
cin>>f[i]>>t[i]>>w[i];
}
;i<=N;i++) d[i]=inf;
d[]=;
;i<=N-;i++){//最短路径最多经过N-1个节点 需要N-1轮松弛
;j<M;j++){//枚举所有的边
int x=f[j],y=t[j];
if(d[x]<inf) d[y]=min(d[y],d[x]+w[j]);
}
}
cout<<d[N];
;
}
可以用队列进行优化，代替上面的循环检查（代码来自 刘汝佳《算法竞赛入门经典》）
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
<<;
;
struct Edge{
int from,to,dist;
};
vector<Edge> edges;
vector<int> G[maxn];
int N,M;
int inq[maxn]/*在队列里的标记*/,cnt[maxn]/*某个节点进入队列的次数，也就是松弛的次数*/;
int d[maxn];
bool bellman_ford(int s){
queue<int> Q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
;i<=N;i++) d[i]=inf;
d[s]=;inq[s]=;Q.push(s);
while(!Q.empty()){
int u=Q.front();Q.pop();
inq[u]=;//出队
;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(d[u]<inf&&d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
if(!inq[e.to]){
Q.push(e.to);inq[e.to]=;//入队
if(++cnt[e.to]>N) return false;
}
}
}
}
return true;
}
int main()
{
int f,t,dd;
cin>>N>>M;
;i<M;i++){
cin>>f>>t>>dd;
edges.push_back((Edge){f,t,dd});
int m=edges.size();
G[f].push_back(m-);
}
))//起点是1
cout<<d[N];//终点是N
else cout<<"Impossible!";//存在负圈
;
}