本文转自：http://blog.csdn.net/u012469987/article/details/38714081
Bellman-Ford算法是一种求单源最短路算法，时间复杂度：O(V * E)（V为图的节点数，E为图的边数），效率很低，但比起dijkstra算法，它可以处理负权边，而且能判断源点是否有负权环（floyd算法只能求最短路不能判断有无），即从源点经过一段路后回到原点有无负权和。
Bellman-ford算法：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define NMAX 2502
#define INF 0x7F7F7F7F
#define eps 10^(-6)
#define MEM(a) memset(a,0,sizeof(a));
#define MEM_MAX(a) memset(a,INF,sizeof(a));
#define FOR(i,n) for(int i=0;i<n;i++)
#define FIN freopen("in.txt","r",stdin);
#define FOUT freopen("out.txt","w",stdout);struct node
{int u,v,w; //边的信息
}edge[NMAX*2+201];
int dis[NMAX]; //源点到各点距离
int N,M,W; //N:节点数，M：正权双向边数，W：负权边数
int cnt; //总边数：不等于M+W，因为双向边要算两条边
int bellman_ford(int src)
{for(int i=1;i<=N;i++)dis[i] = INF;dis[src] = 0;for(int i=1;i<N;i++){bool flag = false;for(int j=1;j<=cnt-1;j++){if( dis[edge[j].u] + edge[j].w < dis[edge[j].v] ){dis[edge[j].v] = dis[edge[j].u] + edge[j].w;flag = true; }}if(!flag) //优化：如果没一条边更新，则最短路完成或有边不可达break;}for(int i=1;i<=cnt-1;i++)if(dis[edge[i].u] + edge[i].w < dis[edge[i].v])return 0;return 1;
}int main()
{int u,v,w,f,M,W;scanf("%d",&f);while(f--){cnt = 1;scanf("%d%d%d",&N,&M,&W);for(int i=1;i<=M;i++){scanf("%d%d%d",&u,&v,&w);edge[cnt].u = u;edge[cnt].v = v;edge[cnt++].w = w;edge[cnt].v = u;edge[cnt].u = v;edge[cnt++].w = w;}for(int i=1;i<=W;i++){scanf("%d%d%d",&u,&v,&w);edge[cnt].u = u;edge[cnt].v = v;edge[cnt++].w = -w; //负权}if(bellman_ford(1))printf("NO\n");elseprintf("YES\n");}return 0;
}