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