Tìm đường đi ngắn nhất trên đồ thị bằng ngôn ngữ C- thuật toán Dijkstra

Tìm đường đi ngắn nhất trên đồ thị bằng ngôn ngữ C – thuật toán Dijkstra

	/*******************************************
	Tim Duong Di ngan Nhat tren Do Thi
	******************************************* */

 #include <stdio.h>
 #include <conio.h>
 #include <stdlib.h>
 #include <math.h>
 
 #define Max 50

int final[Max];
int V;		// So Dinh
int start, end;	// Diem Xuat Phat va Ket Thuc

void Init (int CP[Max][Max]){
	int i, j;
	FILE *f = fopen ("MaTranTrongSo.txt", "r");
	fscanf(f, "%d", &V);
	printf("\n	Bai Toan Tim Duong Di Ngan Nhat Tren Do Thi - ShortestPath");
	printf("\n Do Thi Co %d Dinh", V);
	printf("\n Ma Tran Chi Phi Tren Do Thi la: ");
	for (i = 1; i <= V; i++){
		printf("\n");
		for (j = 1; j <= V; j++){
			fscanf(f, "%d", &CP[i][j]);
			printf(" %2d", CP[i][j]);
			if (CP [i][j] == 0)
				CP[i][j] = 32000;
		}
	}
	fclose(f);
}

void Display (int truoc[Max], int d[Max]){
	int i, j;
	printf("\n Duong Di Ngan Nhat tu %d den %d la: ", start, end);
	printf(" %d <-- ", end);
	i = truoc[end];
	
	while (i != start){
		printf("%d <-- ", i);
		i = truoc[i];
	}
	
	printf("%d", start);
	printf("\n Do Dai Duong Di la: %d", d[end]);
	getch();
}

void Dijkstra (int CP[Max][Max], int truoc[Max], int d[Max]){
	int u, v, minp;
	printf("\n Nhap vao Vi Tri Xuat Phat: "); scanf("%d", &start);
	printf("\n Nhap vao Vi Tri Dich: "); scanf("%d", &end);
	
	for (v = 1; v <= V; v++){
		d[v] = CP[start][v];
		truoc[v] = start;
		final[v] = 0;
	}
	
	truoc[start] = 0;
	d[start] = 0;
	final[start] = 1;
	
	while (!final[end]){
		minp = 2000;
		for (v = 1; v <= V; v++){
			if (!final[v] && (minp > d[v])){
				u = v;
				minp = d[v];
			}
		}
		
		final[u] = 1;			// u la Dinh co Nhan Temp Nho Nhat
		if (!final[end]){
			for (v = 1; v <= V; v++){
				if (!final[v] && (d[u] + CP[u][v] < d[v])){
					d[v] = d[u] + CP[u][v];
					truoc[v] = u;
				}
			}
		}
	}
}

int main (){
	int CP[Max][Max];	// Ma Tran Chi Phi
	int truoc[Max] = {};
	int d[Max] = {};	// Do Dai Duong Di
	
	Init (CP);
	Dijkstra(CP, truoc, d);
	Display (truoc, d);
	return 0;
}