最短経路のディジェストラ(Dijkstra)アルゴリズム

用事がないので、前の簡単なアルゴリズムを整理します.例えば、問題のように、今回は最短経路のDijkstraアルゴリズムを整理します.Dijkstraアルゴリズムは貪欲戦略に基づくアルゴリズムであり,単一ソース点経路を計算する際に比較的実用的である.図論のこれらのコードのテストデータは冗長なので、私はファイルを読む形式でこれらの値を取得して、読者は参考にすることができます.コードは次のとおりです.

#include 
#include 
using namespace std;
const int N = 5;
const int Max = 65535;
int Dijkstra(int start, int end, int G[][N]);
int main(){
	int n, line;
	freopen("input.txt", "r", stdin);
	cin >> n >> line;
	
	int G[N][N] = {0};
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			G[i][j] = Max;
		}
	}
	int p, q, length;
	
	for (int i = 0; i < line; i++){
		cin >> p >> q >> length;
		G[p][q] = length;
		G[q][p] = length;
	}
	
	int start, end;
	cin >> start >> end;
	
	cout << Dijkstra(start, end, G);
	
	return 0;
}
int Dijkstra(int start, int end, int G[][N]){
	int *s = new int[N];
	int *d = new int[N];
	//     
	for (int i = 0; i < N; i++){
		s[i] = 0;
		d[i] = G[start][i];
	}
	s[start] = 1;
	d[start] = 0;
	
	int select = start, temp;

	for (int i = 0; i < N; i++){
		temp = Max;
		//    
		for (int j = 0; j < N; j++){
			if (temp > d[j] && s[j] == 0){
				temp = d[j];
				select = j;
			}
		}	
			s[select] = 1;
		//       	
		for (int k = 0; k < N; k++){
		    int newvalue = G[select][k] + d[select];
			if (newvalue < d[k]){
		    	d[k] = newvalue;
			}	
		}
	} 
	return d[end];
}

テストデータはinput.に保存すべきである.txt、テストデータは以下の通りです.
5 7 0 1 10 0 3 30 0 4 100 1 2 50 2 4 10 3 2 20 3 4 60 0 1
ここで、第1行は2つのデータを含み、n,lineはそれぞれ頂点数と辺数を表し、次にline行データは対応する辺と重み値を表し、最後の行の2つのデータstartとendはそれぞれ開始点と終了点を表す.