/*Bellman-Ford算法偽代碼：for(i=0;i<n-1;i++)//執(zhí)行n-1輪操作，其中n為頂點數(shù){	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;//說明圖中有從源點可達的負環(huán)	}}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為鄰接邊的邊權(quán)};vector<Node> Adj[MAXV];//圖G的鄰接表int n;//n為頂點數(shù)，MAXV為最大頂點數(shù)int d[MAXV];//起點到達各點的最短路徑長度bool Bellman(int s)//s為源點{	fill(d, d + MAXV, INF);	d[s] = 0;//起點s到達自身的距離為0			 //以下為求解數(shù)組d的部分	for (int i = 0; i < n - 1; i++)//執(zhí)行n-1輪操作，n為頂點數(shù)	{		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;//鄰接邊的權(quán)				if (d[u] + dis < d[v])//以u為中介點可以使d[v]更小				{					d[v] = d[u] + dis;//松弛操作				}			}		}	}	//以下為判斷負環(huá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;//鄰接邊的邊權(quán)			if (d[u] + dis < d[v])//如果仍可以被松弛			{				return false;//說明圖中有從源點可達的負環(huán)			}		}	}	return true;//數(shù)組d的所有值都已經(jīng)達到最優(yōu)}/*實質(zhì)是對最短路徑樹的逐層松弛*/