/* Bellman-Ford算法伪代码： for(i=0;in-1;i++)//执行n-1轮操作，其中n为顶点数 { for(each edge u-v)//每轮操作都遍历所有边 { if(d[u]+length[u-v]d[v])//以u为中介点可以使d[v]更小 { d[v] = d[u] + length[u-v];/
Bellman-Ford算法伪代码：
for(i=0;i<n-1;i++)//执行n-1轮操作，其中n为顶点数
{
for(each edge u->v)//每轮操作都遍历所有边
{
if(d[u]+length[u->v]<d[v])//以u为中介点可以使d[v]更小
{
d[v] = d[u] + length[u->v];//松弛操作
}
}
}
for(each edge u->v)//对每条边进行判断
{
if(d[u] + length[u->v]<d[v])//如果仍可以被松弛
{
return false;//说明图中有从源点可达的负环
}
}
return true;
*/
//下面是完整Bellman-ford算法的代码，图是邻接表形式，时间复杂度为O(VE)
//若是邻接矩阵形式，时间复杂度会到O(V^3)
#include<vector>
#include<algorithm>
using namespace std;
const int MAXV = 1000;
const int INF = 1000000000;
struct Node
{
int v, dis;//v为邻接边的目标顶点，dis为邻接边的边权
};
vector<Node> Adj[MAXV];//图G的邻接表
int n;//n为顶点数，MAXV为最大顶点数
int d[MAXV];//起点到达各点的最短路径长度
bool Bellman(int s)//s为源点
{
fill(d, d + MAXV, INF);
d[s] = 0;//起点s到达自身的距离为0
//以下为求解数组d的部分
for (int i = 0; i < n - 1; i++)//执行n-1轮操作，n为顶点数
{
for (int u = 0; u < n; u++)//每轮操作都遍历所有的边
{
for (int j = 0; j < Adj[u].size(); j++)
{
int v = Adj[u][j].v;//邻接边的顶点
int dis = Adj[u][j].dis;//邻接边的权
if (d[u] + dis < d[v])//以u为中介点可以使d[v]更小
{
d[v] = d[u] + dis;//松弛操作
}
}
}
}
//以下为判断负环的代码
for (int u = 0; u < n; u++)//对每条边进行判断
{
for (int j = 0; j < Adj[u].size(); j++)
{
int v = Adj[u][j].v;//邻接表的顶点
int dis = Adj[u][j].dis;//邻接边的边权
if (d[u] + dis < d[v])//如果仍可以被松弛
{
return false;//说明图中有从源点可达的负环
}
}
}
return true;//数组d的所有值都已经达到最优
}
/*
实质是对最短路径树的逐层松弛
*/