/*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的所有值都已經達到最優}/*實質是對最短路徑樹的逐層松弛*/