Dijkstraアルゴリズム-方法、アルゴリズム、コードと正確性の証明

Dijkstraアルゴリズム

						-  、  、         

							  

    Dijkstra  ，    、  、         C++   。

§1 Dijkstraアルゴリズムの方法紹介
アルゴリズムの適用範囲:Dijkstraアルゴリズムは、すべてのエッジの重みが非負の値であることを要求する重み付きの問題である図面上の単一ソース最短パスの問題を解決します.
Dijkstraアルゴリズム(方法):

    ：     G=(V,E)  ，   v_i  v_j      w[i][j]，      v_0           。（      ）

1.    v_0， V_G={ v_0  }， dis[i]   v_i    v_0     ，     ，  v_i   v_0       ，     ∞（dis[i] = dis[0][i]）；

2.         ，    V_G    dis[i]      v_i，     V_G ，     v_i      V_G      (dis[j]=min{dis[j],dis[i]+w[i][j]})

3.  2        V_G。

§2 Dijkstraアルゴリズム実装

   ： Dijkstra     
  ：G             
  ：             
function Dijkstra(Graph, source):
       create vertex set Q
      for each vertex v in Graph:             //   
          dis[v] ← INFINITY                 //                      pre[v] ← UNDEFINED         //         （    ）
          // All nodes initially in Q (unvisited nodes)
          add v to Q    
 
      dis[source] ← 0                        // Distance from source to source
      
	while Q is not empty:
		// Node with the least distance will be selected first
        u ← vertex in Q with min dis[u] 
        remove u from Q 
          
        for each neighbor v of u:           // where v is still in Q.
           alt ← dis[u] + length(u, v)
           // A shorter path to v has been found
           if alt < dis[v]:               
                dis[v] ← alt 
             pre[v] ← u 

     return dis[], pre[]

§3 DijkstraアルゴリズムC++実装

//        
//     0   ，        
#define maxPath  0x7FFF
#define maxNum 1000

int node_num, line; ////          
int pre[maxNum] = {};     //            
int weight[maxNum][maxNum];   //               
int path[maxNum] = {}; //                

//Dijkstra    ：

void Dijkstra(){ 
	path[0] = 0; //source
	bool vertex[node_num] = {};
	vertex[0] = true;

	for(int i = 0;i < node_num;i++) 
		if(weight[0][i] != 0)		path[i] = weight[0][i];
		else path[i] = maxPath;

	int minPath = maxPath , minPath_index = 0 , preIndex = 0;
	for(int j = 0;j < node_num;j++){
		
		minPath = maxPath;			
		preIndex = minPath_index;  //              
	
		for(int i = 0;i < node_num;i++){
			if(i == preIndex)  continue;
else if(!vertex[i] && weight[preIndex][i] != 0 && \
	 path[i] > path[preIndex] + weight[preIndex][i]){
				path[i] = path[preIndex] + weight[preIndex][i];
				pre[i] = preIndex;
				if(path[i] < minPath)
					minPath_index = i,minPath = path[i];	
			}
		}
			
		for(int k = 1;k < node_num;k++)
			if(path[k] < minPath && !vertex[k]){
				minPath_index = k ;
				minPath = path[k] ;
				preIndex = pre[k];
			}
		vertex[minPath_index] = true;
	}
} 


//get the path
void findSmallestPath(int indexOfNode){
	if(indexOfNode != 0)
		findSmallestPath(pre[indexOfNode]);
	if(indexOfNode != node_num-1)	cout << indexOfNode << " -> ";
	else cout << indexOfNode << endl;
}

//     
//0 source，node_num sink 
int main(){
	cout <<"Please enter the num of the vertex : " << endl;
	cin >> node_num ;
	cout << "Please enter the num of the line : " << endl;
	cin >> line;
	cout << "Please enter the line in order : " << endl;
	for(int i = 0;i < line;i++){
		int first_node , second_node , w;
		cin >> first_node >> second_node;
		cin >> w; 	
		weight[first_node][second_node] = weight[second_node][first_node] = w;
	} 
	Dijkstra();
	cout << "The smallest weight : " << path[node_num-1] << endl;	 
	cout << "Show The Path : ";
	findSmallestPath(node_num-1);
	return 0;
}

§4 Dijkstraアルゴリズムの正確性の証明
Dijkstraアルゴリズムは、常に「最近」または「最も軽い」ノードを選択して集合Vに加え、貪欲なポリシーを使用する.証明はすでにアクセスしたノード数学の帰納法によって証明された.(注:アクセスしたポイントは、集合に参加したポイントを示します)
不変の前提:すでにアクセスされた各ポイントvについて、dis[v]はソースからそのポイントまでの最短距離を表す.まだアクセスされていないノードuの場合、dis[u]は、現在アクセスされているノードを介してソースポイントからそのポイントまでの最短距離を表す(パスが1つしか存在しない場合、無限大である場合、現在の最短パスdis[u]が未アクセスノードuの最短パスであるとは仮定しない).
1.2つのノードしかない場合、1つのソースポイント、1つの集約ポイント、結論は明らかに成立する.
2.n-1個のノードを仮定する場合.次に、ノードuが非アクセスノードの中で最小のdis[u]を有するノードであり、dis[u]=dis[v]+length[v,u]であるエッジvuを選択する.dis[u]は必ずソースポイントからすべての未アクセスの中で最も短いパス長である.なぜなら、より短いパスが存在する場合、wがそのパス上で最初に未アクセスのノードであると仮定すると、dis[w]>dis[u]と仮定するのと矛盾するため、dis[u]は必ずソースポイントからすべての未アクセスノードまでの最短パス長である.同様に、非アクセスノードを使用しない場合、ノードuへのより短いパスが存在し、パス上の最後のノードがwである場合、前提と矛盾するdis[u]=dis[w]+length[w,u]を有する.終了点uを処理した後、残りのアクセスされていないノードについて同じ処理を行うことで、ソース点からその点への経路が最も短いことが保証される.そこでDijkstraアルゴリズムが成立した.
参考文献:

Dijkstra’s algorithm wiki

『アルゴリズム導論』