Bellman - Ford算法是求含<b>负权图</b>的单源最短路径算法，效率很低，但代码很容易写。其原理为持续地进行松弛（原文是这么写的，为什么要叫松弛，争议很大），在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。Bellman - Ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。
struct edge {
int from,to;
int cost;
};
edge es[MAXE];
int d[MAXV]; // d[i]表示d[start]到i点的最短距离
int v, e; // 顶点数， 边数
void Bellman_Ford(int s) {
fill(d + 1, d + v + 1, INF);
d[s] = 0;
for (int i = 1; i <= v; ++i) {
bool update = false;
for (int j = 0; j < e; ++j) {
if (d[es[j].from] != INF) {
d[es[j].to] = min(d[es[j].to], d[es[j].from] + es[j].cost);
update = true;
}
}
if (!update)
break;
}
bool flag = false;
for (int i = 0; i < es.size(); ++i) {
if (d[es[i].to] > d[es[i].from] + es[i].cost) {
flag = true;
break;
}
}
if (flag)
cout << "图包含了负权环";
}
