Bellman-Ford算法能解决负权边的图，就是说能够来判断存在负环。
先来看一下核心代码：
dis[i] 为源点到i点的最短路
for(k = 1; k <= n-1; k++) //n为顶点的个数for(int i = 1; i <= m; i++) //m为边的条数if(dis[v[i]] > dis[u[i]] + w[i]) //u[i]为第i条边的起点，v[i]为第i条边的终点，w[i]为第i条边的权重（就是长度）dis[v[i]] = dis[u[i]] + w[i]最外层一共循环了n-1次，内循环循环了m次，
内循环的意思就是：通过每一条边来松弛每两个顶点之间的距离。
外循环n-1次的原因：因为在一个包含n个顶点的图中，任意两点之间的最短路最多包含n-1条边。
有些特别爱思考的同学又会发出一个疑问：真的最多只能包含n-1条边？最短路径中不可能包含回路么？
答案是：不可能！最短路径肯定是一个不包含回路的简单路径。回路分为正权回路（即回路权值之和为正）和负权回路（即回路权值之和为负）。分别讨论一下为什么这两种回路都不可能有。如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径。如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径。因此，最短路径肯定是一个不包含回路的简单路径，即最多包含n-1条边，所以进行n-1轮松弛就可以了。
来个题实战下：poj3259Wormholes
#include<iostream>
using namespace std;
int u[5400], v[5400], w[5400], dis[550];
int main()
{int f, N, M, W;while(cin >> f){while(f--){cin >> N >> M >> W;for(int i = 0; i < M*2; i+=2){cin >> u[i] >> v[i] >> w[i];u[i+1] = v[i];v[i+1] = u[i];w[i+1] = w[i];}for(int i = 2*M; i < 2*M+W; i++){cin >> u[i] >> v[i] >> w[i];w[i] *= -1;}fill(dis, dis+540, 0x3f3f3f3f);dis[1] = 0;for(int i = 0; i < N-1; i++){bool check = false;for(int j = 0; j < 2*M+W; j++){if(dis[v[j]] > dis[u[j]] + w[j]){dis[v[j]] = dis[u[j]] + w[j];check = true;//经过一轮所有边的松弛之后如果没有得到任何一次松弛，check就为false,因为每次都是通过所有边松弛，这次松不了，那么下次也松弛不了}}if(!check)break;}bool flag = false;for(int i = 0; i < 2*M+W; i++){if(dis[v[i]] > dis[u[i]] + w[i]){dis[v[i]] = dis[u[i]] + w[i];flag = true;}if(flag)//判断是否存在负环，也就是说在进行N-1轮松弛后， 仍然可以继续松弛成功，那么此图必然存在负权回路。在之前证明中已经讨论过，如果一个图没有负权回路，那么最短路径所包含的边最多为N-1条，即进行N-1轮松弛之后最短路不会再发生变化。如果在N-1轮松弛之后最短路仍然会发生变化，则该图必然存在负权回路。break;}if(flag)cout << "YES\n";elsecout << "NO\n";}}return 0;
}Bellman-Ford的队列优化解决：
每次仅对最短路程发生变化了的点的相邻边执行松弛操作。但是如何知道当前哪些点的最短路程发生了什么变化呢？这里可以用一个队列来维护这些点。
每次选取队首顶点u（随意命名的），对顶点u的所有出边进行松弛操作。例如有一条u->v的边，如果通过u->v这条边是的源点到顶点v的最短路程变短（dis[u] + edge[u][v] < dis[v]）,且顶点v不在当前队列中，就将顶点v放入队尾。需要注意的是，同一个顶点同事在队列中出现多次是毫无意义的，所以需要一个标记数组进行判重（判断哪些点已经在队列中）。在对顶点u的所有出边松弛完毕之后，就将顶点u出队。接下来不断从队列中取出队首顶点再进行如上操作，直到队列空为止。
判断有无负环： 如果某个点进入队列的次数超过N次则存在负环
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct node
{int en;int w;node (){}node(int a, int b){en = a;w = b;}
};
vector<node> a[505];
int dis[550], c[550];
bool vis[550];
int main()
{int N, M, W, f, u, v, w;while(cin >> f){while(f--){cin >> N >> M >> W;for(int i = 1; i <= N; i++)a[i].clear();for(int i = 0; i < M*2; i += 2){cin >> u >> v >> w;a[u].push_back(node(v, w));a[v].push_back(node(u, w));}for(int i = M*2; i < M*2 + W; i++){cin >> u >> v >> w;a[u].push_back(node(v, -w));}fill(dis, dis+N +1, 0x3f3f3f3f);dis[1] = 0;memset(c, 0, sizeof(c));memset(vis, false, sizeof(vis));vis[1] = true;int OK = 1;c[1] = 1;queue<int> q;q.push(1);while(!q.empty()){int x;x = q.front();q.pop(); vis[x] = false;for(int i = 0; i < a[x].size(); i++){node tem = a[x][i];if(dis[tem.en] > dis[x] + tem.w){dis[tem.en] = dis[x] + tem.w;if(!vis[tem.en]){vis[tem.en] = true;c[tem.en]++;q.push(tem.en);if(c[tem.en] > N)OK = 0;}}}if(OK == 0)break;}if(OK == 0)cout << "YES\n";elsecout << "NO\n";}}return 0;
}