Bellman-Ford算法

/*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的所有值都已经达到最优}/*实质是对最短路径树的逐层松弛*/