/*由于Bellman-Ford算法的每輪操作都需要操作所有的邊，顯然這其中會有大量無意義的操作，嚴(yán)重影響了算法的性能。于是注意到，只有當(dāng)某個頂點(diǎn)u的d[u]值改變時，從它出發(fā)的邊的鄰接點(diǎn)v的d[v]值才有可能改變。由此可以進(jìn)行一個優(yōu)化：建立一個隊(duì)列，每次將隊(duì)首頂點(diǎn)取出，然后對從u出發(fā)的所有邊u->v進(jìn)行松弛操作，也就是判斷d[u]+length[u->v]<d[v]是否成立，如果成立，則用d[u]+length[u->v]覆蓋d[v]，于是d[v]獲得更優(yōu)的值，此時如果v不在隊(duì)列中，就把v加入隊(duì)列。這樣操作直到隊(duì)列為空（說明圖中沒有從源點(diǎn)可達(dá)的負(fù)環(huán)），或某個頂點(diǎn)的入隊(duì)次數(shù)超過V-1（說明圖中存在從原點(diǎn)可達(dá)的負(fù)環(huán)）。以下是偽代碼：queue<int> Q;源點(diǎn)s入隊(duì);while(隊(duì)列非空){	取出隊(duì)首元素u；	for(u的所有鄰接邊u->v)	{		if(d[u]+dis<d[v])		{			d[v] = d[u] +　dis;			if(v當(dāng)前不在隊(duì)列)			{				v入隊(duì)；				if(v入隊(duì)次數(shù)大于n-1)				{					說明有可達(dá)負(fù)環(huán)，return;				}			}		}	}}這種優(yōu)化后的算法被稱為SPFA（Shortest Path Faster Algorithm）,期望時間復(fù)雜度為O(kE),k為常數(shù)，很多情況下不超過2，經(jīng)常性優(yōu)于堆優(yōu)化的Dijkstra算法。若原圖中存在從源點(diǎn)可達(dá)的負(fù)環(huán)則SPFA的時間復(fù)雜度會退化成O(VE)。*///下面是鄰接表形式的圖的SPFA代碼#include<vector>#include<queue>#include<algorithm>using namespace std;const int MAXV = 1000;const int INF = 1000000000;struct Node{	int v, dis;};vector<Node> Adj[MAXV];//圖G的鄰接表int n, d[MAXV], num[MAXV];//num數(shù)組記錄頂點(diǎn)的入隊(duì)次數(shù)bool inq[MAXV];//頂點(diǎn)是否在隊(duì)列中bool SPFA(int s){	//初始化部分	memset(inq, false, sizeof(inq));	memset(num, 0, sizeof(num));	fill(d, d + MAXV, INF);	//源點(diǎn)入隊(duì)部分	queue<int>Q;	Q.push(s);//源點(diǎn)入隊(duì)	inq[s] = true;//源點(diǎn)已入隊(duì)	num[s]++;//源點(diǎn)入隊(duì)次數(shù)加1	d[s] = 0;//源點(diǎn)的d值為0	//主體部分	while (!Q.empty())	{		int u = Q.front();//隊(duì)首頂點(diǎn)編號為u		Q.pop();//出隊(duì)		inq[u] = false;//設(shè)置u為不在隊(duì)列中		//遍歷u的所有鄰接邊v		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])			{				d[v] = d[u] + dis;				if (!inq[v])//如果v不在隊(duì)列中				{					Q.push(v);//v入隊(duì)					inq[v] = true;//設(shè)置v為在隊(duì)列中					num[v]++;//v的入隊(duì)次數(shù)加1					if (num[v] >= n) return false;//有可達(dá)負(fù)環(huán)				}			}		}	}	return true;//無可達(dá)環(huán)}/*注意上述SPFA代碼是BFS版本，當(dāng)然也可以將隊(duì)列換成棧以實(shí)現(xiàn)DFS版本的SPFA，對判環(huán)有奇效。還有，可以將隊(duì)列換成優(yōu)先隊(duì)列以加快速度。當(dāng)然還可以換成deque（雙端隊(duì)列），使用SLF或LLL優(yōu)化。SPFA算法有兩個優(yōu)化算法 SLF 和 LLL： SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)<dist(i)，則將j插入隊(duì)首，否則插入隊(duì)尾。 LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i，隊(duì)列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對進(jìn)行松弛操作。SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。在實(shí)際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。*/