Bellman算法和SPFA算法

Dijkstra算法比較快速，但是如果遇到負邊就無能為力了，而Bellman算法可以解決負邊問題，隻要不是負環。

這個算法資料結構沒有講過，他主要是每次對是以邊進行松弛操作，進行n-1次得到最短路徑。

其原理如下所述：

首先指出，圖的任意一條最短路徑既不能包含負權回路，也不會包含正權回路，是以它最多包含|n-1條邊。

其次，從源點s可達的所有頂點如果存在最短路徑，則這些最短路徑構成一個以s為根的最短路徑樹。Bellman-Ford算法的疊代松弛操作，實際上就是按頂點距離s的層次，逐層生成這棵最短路徑樹的過程。

在對每條邊進行1遍松弛的時候，生成了從s出發，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯的那些頂點的最短路徑；對每條邊進行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經過2條邊相連的那些頂點的最短路徑……。因為最短路徑最多隻包含|v|-1 條邊，是以，隻需要循環|v|-1 次。

如果沒有負權回路，由于最短路徑樹的高度最多隻能是|v|-1，是以最多經過|v|-1遍松弛操作後，所有從s可達的頂點必将求出最短距離。如果 d[v]仍保持 +∞，則表明從s到v不可達。

如果有負權回路，那麼第 |v|-1 遍松弛操作仍然會成功，這時，負權回路上的頂點不會收斂。

根據這個原理寫出代碼如下：

bool Bellman(int s,int n){
	
	fill(dis,dis+n,inf);
	dis[s]=0;
	
	for(int i=0;i<n-1;i++){//n-1此松弛操作 
	    int flag=1;
		for(int u=0;u<n;u++) 
		{
			for(int j=0;j<Adj[u].size();j++)
			{
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x])
			 {dis[x]=dis[u]+Adj[u][j].weight;//松弛操作  
			 flag=0;
			}	
			}
		}
		if(flag)return true;//如果這一輪沒有被松弛，直接退出 
      }
	for(int u=0;u<n;u++) //判斷是否存在負環 
		{
			for(int j=0;j<Adj[u].size();j++)
			{
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x])
			  return false;//還能松弛存在負環，失敗 
			}	
		}
		return true;	
	}
           

雖然了解簡單但是這個算法耗時較大，每一輪都要周遊所有邊，其實由于一個頂點u的d[u]改變時，以此點出發的鄰接點d[v]才可能改變，結合Bellman樹的形成過程可以類比層次周遊，用一個隊列存放結點，每拿出一個結點對鄰接點松弛，如果能松弛且不在隊列裡就讓其入隊，直到隊空（說明無負環，）或者某個結點入隊超過n-1次，說明有負環。這就是SPFA算法，一般比Dijkstra算法還要快，比較高效。代碼如下：

bool SPFA(int s,int n){
		fill(inq,inq+n,false);//記錄是否入隊
		fill(num,num+n,0);//記錄入隊次數
		fill(dis,dis+n,inf);
		queue<int>q;
		q.push(s);
		inq[s]=true;
		num[s]++;
		dis[s]=0;
		while(!q.empty()){
			int u=q.front();q.pop();
			inq[u]=false;
			for(int j=0;j<Adj[u].size();j++){
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x]){
			  dis[x]=dis[u]+Adj[u][j].weight;
				if(!inq[x])
				{
					q.push(x);
					num[x]++;
					inq[x]=true;
					if(num[x]>n-1)//負環
					return false;
				}
			}
			}		
		}
	return true;	
	}
           

此外關于最短路徑還有一個Floyd算法，這裡打包帶走，下面是三個算法的全體代碼：

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

const int maxv=101;
const int inf=10000000;
struct node{
	int v,weight;
};

vector<node>Adj[maxv] ;
int dis[101];

//bellman算法 

bool Bellman(int s,int n){
	
	fill(dis,dis+n,inf);
	dis[s]=0;
	
	for(int i=0;i<n-1;i++){//n-1此松弛操作 
	    int flag=1;
		for(int u=0;u<n;u++) 
		{
			for(int j=0;j<Adj[u].size();j++)
			{
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x])
			 {dis[x]=dis[u]+Adj[u][j].weight;//松弛操作  
			 flag=0;
			}	
			}
		}
		if(flag)return true;//如果這一輪沒有被松弛，直接退出 
      }
	for(int u=0;u<n;u++) //判斷是否存在負環 
		{
			for(int j=0;j<Adj[u].size();j++)
			{
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x])
			  return false;//還能松弛存在負環，失敗 
			}	
		}
		return true;	
	}
	
	
	
	//SPFA算法
	bool inq[maxv] ;
	int num[maxv];
	
	bool SPFA(int s,int n){
		fill(inq,inq+n,false);
		fill(num,num+n,0);
		fill(dis,dis+n,inf);
		queue<int>q;
		q.push(s);
		inq[s]=true;
		num[s]++;
		dis[s]=0;
		while(!q.empty()){
			int u=q.front();q.pop();
			inq[u]=false;
			for(int j=0;j<Adj[u].size();j++){
				int x=Adj[u][j].v;
			if(dis[u]+Adj[u][j].weight<dis[x]){
			  dis[x]=dis[u]+Adj[u][j].weight;
				if(!inq[x])
				{
					q.push(x);
					num[x]++;
					inq[x]=true;
					if(num[x]>n-1)
					return false;
				}
			}
			}		
		}
	return true;	
	}


//floyd算法
int d[maxv][maxv]	;

void floyd(int n){
	for(int k=0;k<n;k++)
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	if(d[i][k]!=inf&&d[k][j]!=inf&&d[i][k]+d[k][j]<d[i][j])
	d[i][j]=d[i][k]+d[k][j];
}
	
	
	int main(){
		int n,m,s,t;
	int x,y,w;
	node temp;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=0;i<m;i++){
		scanf("%d%d%d",&x,&y,&w); 
		temp.weight=w;
		temp.v=x;
		Adj[y].push_back(temp);
		temp.v=y;
		Adj[x].push_back(temp);
	}
	if(SPFA(s,n)) {
		for(int i=0;i<n;i++)
		printf("%d ",dis[i]);
	}
		return 0;
	}