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;
}