/*Bellman-Ford算法偽代碼：for(i=0;i<n-1;i++)//執(zhí)行n-1輪操作，其中n為頂點(diǎn)數(shù){	for(each edge u->v)//每輪操作都遍歷所有邊	{	if(d[u]+length[u->v]<d[v])//以u(píng)為中介點(diǎn)可以使d[v]更小		{			d[v] = d[u] + length[u->v];//松弛操作		}	}}for(each edge u->v)//對(duì)每條邊進(jìn)行判斷{	if(d[u] + length[u->v]<d[v])//如果仍可以被松弛	{		return false;//說明圖中有從源點(diǎn)可達(dá)的負(fù)環(huán)	}}return true;*///下面是完整Bellman-ford算法的代碼，圖是鄰接表形式，時(shí)間復(fù)雜度為O(VE)//若是鄰接矩陣形式，時(shí)間復(fù)雜度會(huì)到O(V^3)#include<vector>#include<algorithm>using namespace std;const int MAXV = 1000;const int INF = 1000000000;struct Node{	int v, dis;//v為鄰接邊的目標(biāo)頂點(diǎn)，dis為鄰接邊的邊權(quán)};vector<Node> Adj[MAXV];//圖G的鄰接表int n;//n為頂點(diǎn)數(shù)，MAXV為最大頂點(diǎn)數(shù)int d[MAXV];//起點(diǎn)到達(dá)各點(diǎn)的最短路徑長度bool Bellman(int s)//s為源點(diǎn){	fill(d, d + MAXV, INF);	d[s] = 0;//起點(diǎn)s到達(dá)自身的距離為0			 //以下為求解數(shù)組d的部分	for (int i = 0; i < n - 1; i++)//執(zhí)行n-1輪操作，n為頂點(diǎn)數(shù)	{		for (int u = 0; u < n; u++)//每輪操作都遍歷所有的邊		{			for (int j = 0; j < Adj[u].size(); j++)			{				int v = Adj[u][j].v;//鄰接邊的頂點(diǎn)				int dis = Adj[u][j].dis;//鄰接邊的權(quán)				if (d[u] + dis < d[v])//以u(píng)為中介點(diǎn)可以使d[v]更小				{					d[v] = d[u] + dis;//松弛操作				}			}		}	}	//以下為判斷負(fù)環(huán)的代碼	for (int u = 0; u < n; u++)//對(duì)每條邊進(jìn)行判斷	{		for (int j = 0; j < Adj[u].size(); j++)		{			int v = Adj[u][j].v;//鄰接表的頂點(diǎn)			int dis = Adj[u][j].dis;//鄰接邊的邊權(quán)			if (d[u] + dis < d[v])//如果仍可以被松弛			{				return false;//說明圖中有從源點(diǎn)可達(dá)的負(fù)環(huán)			}		}	}	return true;//數(shù)組d的所有值都已經(jīng)達(dá)到最優(yōu)}/*實(shí)質(zhì)是對(duì)最短路徑樹的逐層松弛*/