Hướng dẫn code thuật toán Floyd bằng ngôn ngữ c

Hướng dẫn code thuật toán Floyd bằng ngôn ngữ c

Bạn nhập ma trận bên dưới vào một tập tin có đuôi txt và bỏ nó vào ổ đĩa phù hợp với phần define bên dưới đoạn code.

Ma trận mẫu

#include <stdio.h>
#include <conio.h>
#define MAX 100
#define input “g:/test-1.txt”
#define VOCUC 1000
int Sau_Nut[MAX][MAX];
int L[MAX][MAX];
typedef struct graph{
int n;
int a[MAX][MAX];
}DOTHI;
int DocFile(DOTHI &g,char text[MAX]){
FILE *f;
f=fopen(text,”rt”);
if(f==NULL){
printf(“\n Khong tim thay file”);
return 0;
}
fscanf(f,”%d”,&g.n);
for(int i=0;i<g.n;i++){
for(int j=0; j<g.n;j++)
fscanf(f,”%d”,&g.a[i][j]);
}
fclose(f);
return 1;
}
void XuatDoThi(DOTHI g){
printf(“\n So dinh: %d”,g.n);
printf(“\n Ma tran: \n”);
for(int i=0; i<g.n;i++){
printf(“\t”);
for(int j=0; j<g.n; j++)
printf(“%d “,g.a[i][j]);
printf(“\n”);
}
}
void Floyd(DOTHI g){
int i,j;
for(i=0;i<g.n;i++){
for(j=0;j<g.n;j++){
if(g.a[i][j] >0){
Sau_Nut[i][j] = j;
L[i][j] = g.a[i][j];
}
else{
Sau_Nut[i][j] = -1;
L[i][j] = VOCUC;
}
}
}
for(int k=0; k<g.n;k++){
for(i=0;i<g.n;i++){
for(j=0;j<g.n;j++){
if(L[i][j] > L[i][k] + L[k][j]){
L[i][j] = L[i][k] + L[k][j];
Sau_Nut[i][j] = Sau_Nut[i][k];
}
}
}
}
//xuat ket qua tim duong di ngan nhat s–>f
int S,F;
printf(“Nhap vao dinh bat dau: “);
scanf(“%d”,&S);
printf(“Nhap vao dinh ket thuc: “);
scanf(“%d”,&F);
if(Sau_Nut[S][F] == -1){
printf(“Khong co duong di tu dinh %d den dinh %d la: \n”,S,F);
}
else{
printf(“Duong di ngan nhat tu dinh %d den dinh %d la: \n”,S,F);
printf(“\t%d”,S);
int u=S;
while(Sau_Nut[u][F] != F){
u = Sau_Nut[u][F];
printf(“–>%d”,u);
}
printf(“–>%d”,F);
printf(“\n\Voi tong trong so la %d”,L[S][F]);
}
}
int main(){
DOTHI g;
if(DocFile(g,input)==1){
printf(“\n Doc do thi thanh cong”);
XuatDoThi(g);
printf(“Bam 1 phim bat ki de bat dau tim duong di ngan nhat theo thuat toan Floyd …\n\n”);
getch();
Floyd(g);
}
getch();
}