最短パスアルゴリズムDijkstra&&SPFA&&Floydコード実装テンプレート

本文はすでにこの3種類のアルゴリズムの基本思想を理解した上で創立して、アルゴリズムに対して詳しい説明を行うのではなくて、思想に対して比較的に優秀なコードの実現の総括を行って、直接ACM題目あるいは実際の問題の解決の中で用いることができます.
Dijkstraアルゴリズム:
Dijkstraアルゴリズムは,ソース点を指定し,このソース点から各点への最短経路を求める.Dijkstraアルゴリズムは,エッジを絶えず緩和し,記録を行い,隣接点の経路を更新するたびに,貪欲なような考え方を採用し,2点間の距離を最短の経路とする.
Dijkstraアルゴリズムの欠点は,負の重みエッジを持つことができない値である.

#define INF 0x3f3f3f3
const int MAX_N=200;
int map[MAX_N][MAX_N],vis[MAX_N],dis[MAX_N];//dis            
//    map[][]=INF 
void dijkstr(int x,int m){//x     ，m       
	for(int i=1;i<=m;i++){
		dis[i]=map[x][i];
		vis[i]=0;
      // if(map[x][i]!=INF)
		//pre[i]=x;
		//else
		//pre[i]=-1;
	}
	int p;
	vis[x]=1;
	for(int i=1;i<=m;i++){
	   	int min=INF;
	   	for(int j=1;j<=m;j++){
	   		if(!vis[j]&&dis[j]<min){
		   		min=dis[j];
		   		p=j;
		   	}   	
	   	}
	   	vis[p]=1;
		for(int j=1;j<=m;j++){
			if(!vis[j]&&dis[p]+map[p][j]<dis[j])
			{
              dis[j]=dis[p]+map[p][j];
               //pre[j]=p;
           }
		}	   	
	}
}


int main(){
	int m,n,a,b,c;
	void dijkstr(int x,int n);
	while(cin>>m>>n&&(m||n)){
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++){
			 map[i][j]=INF;
		}
		for(int j=1;j<=n;j++){
			cin>>a>>b>>c;
			map[a][b]=map[b][a]=c;
		}
		dijkstr(1,m);
		cout<<dis[m]<<endl;
      /* int p,len=1;
		p=m;
		while(p>=1)
	    {
           ans[len++]=p;
           p=pre[p];
		}
	   for(int r=len-1;r>=1;r--)
	   cout<<ans[r];*/
	
	}
	return 0;
}

Floydアルゴリズム:
floydアルゴリズムは古典的な動的計画アルゴリズムであり,任意の2点間の最短ルートを求めることができるが,複雑度はO(N 3)であり,複雑度が高く,大量点間の最短ルートの計算には適していない.

//floyd      ，f      ，         
void Floyd()
{
	for(int k = 1; k <= N; k++)	//       k
	{
		for(int i = 1; i <= N; i++)	
		{
			for(int j = 1; j <= N; j++)
			{
				f[i][j] = f[i][j] || (f[i][k] && f[k][j]);	//       
			}
		}
	}
}
//floyd      
void Floyd()
{
	for(int k = 1; k <= N; k++)	//       k
	{
		for(int i = 1; i <= N; i++)	
		{
			for(int j = 1; j <= N; j++)
			{
				if(f[i][j]>f[i][k]+f[k][j])
				f[i][j]=f[i][k]+f[k][j];
			}
		}
	}
}

SPFAアルゴリズム:
単一ソース最短パスに負の重みエッジが存在する場合,このときDijkstraアルゴリズムは使用できない.SPFAは対Bellman_Fordアルゴリズムの最適化は、最適化されるノードを保存するために先進的な先頭キューを使用します.

/*
*      SPFA
*       0(kE)
*        ，            ，     
*          
*/
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
   int v;
   int cost;
   Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
   E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//     
int cnt[MAXN];//         
int dist[MAXN];
bool SPFA(int start,int n)
{
   memset(vis,false,sizeof(vis));
   for(int i=1;i<=n;i++)
   dist[i]=INF;
   vis[start]=true;
   dist[start]=0;
   queue<int>que;
   while(!que.empty())
   que.pop();
   que.push(start);
   memset(cnt,0,sizeof(cnt));
   cnt[start]=1;
   while(!que.empty())
   {
      int u=que.front();
      que.pop();
      vis[u]=false;
      for(int i=0;i<E[u].size();i++)
      {
         int v=E[u][i].v;
         if(dist[v]>dist[u]+E[u][i].cost)
         {
            dist[v]=dist[u]+E[u][i].cost;
            if(!vis[v])
            {
               vis[v]=true;
               que.push(v);
               if(++cnt[v]>n)
			   return false;
               //cnt[i]      ，            
            }
         }
      }
    }
   return true;
}