Dijkstraアルゴリズムは非負の重み値の最短経路の解を実現する(小根スタックを用いて最適化する)

Dijkstraアルゴリズムを用いて非負の重み値の最小値を解くには,n−1ラウンドのループを行い,各ラウンドは,片側条件下で開始ノードv 0から他の各ノードまでの最短距離を求め,隣接するこの点v 1を「処理済み」と表記し,v 1を中継としてv 1に最も近い残りの頂点v 2を見つけ,次にdist[v 2]の値とdist[v 1]+weight[v 1][v 2]を比較し、dist[v 2]が大きい場合はdist[v 2]をdist[v 1]+weight[v 1][v 2]に書き換える.
基本的な実装は次のとおりです.

#include <iostream>
#include <memory.h>
using namespace std;

const int MaxSize=10;

int arr[MaxSize][MaxSize];
int dist[MaxSize];

int numNode=0; //         

//        
void createArr()
{
	//                     
	cin>>numNode;
	for(int i=0;i<numNode;++i)
		for(int j=0;j<numNode;++j)
			cin>>arr[i][j];
}


//         
void Dijkstra(int v0)
{
	memset(dist,0,sizeof(dist));

	//   v0        
	for(int i=0;i<numNode;++i)
		dist[i]=arr[v0][i];

	int pos=0;
	arr[v0][v0]=1; // v0       1
	// numNode-1  v0       
	for(int i=0;i<numNode-1;++i)
	{
		int min=32767;

		//         v0     
		for(int k=0;k<numNode;++k)
		{
			if((dist[k]<min)&&(arr[k][k]!=1))
			{
				pos=k;
				min=dist[k];
			}
		}

		arr[pos][pos]=1; //          1

		// pos     ， if            v0   
		for(int j=0;j<numNode;++j)
		{
			if((arr[j][j]!=1)&&(arr[pos][j]+min<dist[j]))
				dist[j]=arr[pos][j]+min;
		}
	}

	//               
	for(int i=0;i<numNode;++i)
		cout<<dist[i]<<" ";
	cout<<endl;
}

int main()
{
	createArr();

	Dijkstra(0);
}

しかし、上記のコードを分析すると、開始点に最も近いノードを探すときに、何度も比較を繰り返し、優先キューまたは小さなルートスタックを使用して、実際のノードに最も近いノードを迅速に見つけることができます.

#include <iostream>
#include <memory.h>
using namespace std;

/*************************** **********************/

struct Heap
{
	int link; //            
	int dist;//  
	
} heap[60];


//    
void siftDown(int start,int end)
{
	// start         end
	int i=start,j=2*i;
	heap[0]=heap[i]; // heap[0]     i    
	while(j<=end)
	{
		//               ，          j        j     
		if(j<end&&heap[j].dist>heap[j+1].dist) ++j;
		// j     ，    
		if(heap[0].dist<heap[j].dist)		
			break;
		else
		{
			//    
			heap[i]=heap[j];
			i=j;
			j=2*j;
		}
	}
	heap[i]=heap[0];
}

//       
//   start      1  
void siftUp(int start)
{
	int j=start,i=j/2;
	heap[0]=heap[j];
	while(j>0)
	{
		//      ，numID     
		if(heap[i].dist<heap[0].dist)
			break;
		else
		{
			//      
			heap[j]=heap[i];
			j=i;
			i=i/2;
		}
	}
	heap[j]=heap[0];
}

//       
bool insert(int& num,Heap& temp)
{
	++num;
	
	heap[num]=temp;

	siftUp(num);
	
	return true;
}

//    
bool removeMin(int& num,Heap& temp)
{
	if(0==num)
		return false;

	//           
	temp=heap[1];

	heap[1]=heap[num]; //    
	--num;
	siftDown(1,num); //         
	return true;
}


/******************************* ****************************/

const int MaxSize=10;

int arr[MaxSize][MaxSize]; //         
int dist[MaxSize]; //         

int numNode=0; //         



//      
void createArr()
{
	//                     
	cin>>numNode;
	for(int i=0;i<numNode;++i)
		for(int j=0;j<numNode;++j)
			cin>>arr[i][j];
}


//         
void Dijkstra(int v0)
{
	memset(dist,0,sizeof(dist));
	//   v0        
	for(int i=0;i<numNode;++i)
		dist[i]=arr[v0][i];

	arr[v0][v0]=1; // v0       1

	int num=0; //        
	Heap temp;

	// numNode-1  v0       
	for(int i=0;i<numNode-1;++i)
	{
		//               
		for(int k=0;k<numNode;++k)
		{
			if(arr[k][k]!=1)
			{
				temp.link=k;
				temp.dist=dist[k];
				insert(num,temp);
			}
		}

		//            v0     
		if(!removeMin(num,temp)) return;

		int pos=temp.link;
		int min=temp.dist;
		arr[pos][pos]=1; //          1

		// pos     ，          v0   
		for(int j=0;j<numNode;++j)
		{
			if((arr[j][j]!=1)&&(arr[pos][j]+min<dist[j]))
			{
				dist[j]=arr[pos][j]+min;
				//           
				temp.link=j;
				temp.dist=dist[j];
				insert(num,temp);
			}
		}
	}

	//     v0            
	for(int i=0;i<numNode;++i)
		cout<<dist[i]<<" ";
	cout<<endl;
}

int main()
{
	createArr();

	Dijkstra(0);
}