01/10/2018, 09:59
Chương trình minh họa giải thuật Floyd tìm đường đi ngắn nhất trên đồ thị có trọng số
Tiếp tục cho Chương trình minh họa giải thuật Dijkstra tìm đường đi ngắn nhất
/*****************************************************************************
* Chuong trinh C10-2: Chuong trinh minh hoa giai thuat Floyd tim duong di *
* ngan nhat tren do thi co trong so *
* Nguoi viet chuong trinh: Nguyen Hong Chuong *
* Ngay cap nhat moi nhat: 15/3/1999 *
*****************************************************************************/
#include <stdio.h>
#include <conio.h>
#define TOIDA 50
#define VOCUNG 30000
#define TRUE 1
#define FALSE 0
/* Khai bao ma tran trong so cua do thi
weight[i][j] = 0 : neu i = j
weight[i][j] = VOCUNG: neu tren do thi khong co cung <i, j>
weight[i][j] != 0 : tren do thi co cung <i, j> */
int weight[TOIDA][TOIDA];
/* Ma tran D[][]: ma tran cho biet chieu dai ngan nhat di tu nut x den
nut y */
int D[TOIDA][TOIDA];
/* Ma tran P[][]: ma tran cho biet duong di ngan nhat tu nut x den nut y co
qua nut trung gian P[x][y] hay khong:
* Neu P[x][y] == -1: duong di ngan nhat tu nut x den nut y khong
qua nut trung gian
* Neu P[x][y] != -1: duong di ngan nhat tu nut x den nut y co di
qua nut trung gian P[x][y]. */
int P[TOIDA][TOIDA];
int SoNut;
// Khoi dong ma tran trong so cua do thi
void initialize()
{
int i, j;
for(i = 0; i < TOIDA; i++)
for(j = 0; j < TOIDA; j++)
if(i == j)
weight[i][j] = 0;
else
weight[i][j] = VOCUNG;
}
// Tao mot cung tu node1 den node2 voi trong so wt
void joinwt(int node1, int node2, int wt)
{
if(node1 != node2)
weight[node1][node2] = wt;
};
// Xoa cung tu node1 den node2 tren do thi co trong so
void remvwt(int node1, int node2)
{
if(node1 != node2)
weight[node1][node2] = VOCUNG;
};
/* Tac vu floyd: tim duong di ngan nhat tren do thi co trong so, tac vu nay
tinh qua hai ma tran D[][] va P[][]:
- Ma tran D[][]: ma tran cho biet chieu dai ngan nhat di tu nut x den
nut y
- Ma tran P[][]: ma tran cho biet duong di ngan nhat tu nut x den nut y
co qua nut trung gian P[x][y] hay khong:
* Neu P[x][y] == -1: duong di ngan nhat tu nut x den nut y khong
qua nut trung gian
* Neu P[x][y] != -1: duong di ngan nhat tu nut x den nut y co di
qua nut trung gian P[x][y]. */
void floyd()
{
int i, j, k;
// Khoi dong ma tran D va P
for(i = 0; i < SoNut; i++)
for(j = 0; j < SoNut; j++)
{
D[i][j] = weight[i][j];
P[i][j] = -1;
}
// Tinh ma tran D va P o buoc lap thu k
for(k = 0; k < SoNut; k++)
for(i = 0; i < SoNut; i++)
if((D[i][k] > 0) && (D[i][k] < VOCUNG))
for(j = 0; j < SoNut; j++)
if((D[k][j] > 0) && (D[k][j] < VOCUNG))
if(D[i][j] != 0 && D[i][k]+D[k][j] < D[i][j])
{
D[i][j] = D[i][k]+D[k][j];
P[i][j] = k;
}
}
// In lo trinh ngan nhat
void inlotrinh(int x, int y)
{
int r;
if(P[x][y] == -1)
{
printf(" %d -> %d ", x, y);
return;
}
else
{
r = P[x][y];
inlotrinh(x, r);
inlotrinh(r, y);
}
}
// Chuong trinh chinh
void main()
{
int i, j, chucnang, x, y, trongso;
char c;
int p, q, r;
clrscr();
initialize(); // Khoi dong do thi
SoNut = 0;
do
{
// menu chinh cua chuong trinh
printf("
GRAPH - GIAI THUAT FLOYD TIM DUONG DI NGAN NHAT");
printf("
Cac chuc nang cua chuong trinh:
");
printf(" 1: Tao do thi moi
");
printf(" 2: Them mot nut
");
printf(" 3: Them mot cung
");
printf(" 4: Xoa mot cung
");
printf(" 5: Xoa toan bo do thi
");
printf(" 6: Xac dinh so nut co tren do thi
");
printf(" 7: Duyet cac cung
");
printf(" 8: Tim cung
");
printf(" 9: Tim duong di ngan nhat (giai thuat Floyd)
");
printf(" 0: Ket thuc chuong trinh
");
printf("Chuc nang ban chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case 1:
{
initialize();
SoNut = 0;
printf("
Do thi moi co bao nhieu nut: ");
scanf("%d", &SoNut);
printf("Hay nhap cac cung cua do thi (nhap %d %d de ket thuc):
",
SoNut, SoNut);
x = 0;
y = 0;
while(x < SoNut && y < SoNut)
{
printf(" Nhap cung: ");
scanf("%d %d", &x, &y);
if(x < SoNut && y < SoNut)
{
printf(" Trong so cua cung %d %d: ", x, y);
scanf("%d", &trongso);
joinwt(x, y, trongso);
}
};
break;
}
case 2:
{
if(SoNut < TOIDA)
{
SoNut++;
printf("So nut hien co la %d", SoNut);
}
else
printf("Khong the them nut moi");
break;
}
case 3:
{
printf("
Nhap cung can them: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut || x == y)
printf("Khong hop le");
else
{
printf("Trong so cua cung %d -> %d : ", x, y);
scanf("%d", &trongso);
weight[x][y] = trongso;
}
break;
}
case 4:
{
printf("
Nhap cung can xoa: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut || x == y)
printf("Khong hop le");
else
remvwt(x, y);
break;
}
case 5:
{
printf("
Ban co chac khong (c/k): ");
c = getche();
if(c == 'c' || c == 'C')
{
initialize();
SoNut = 0;
}
break;
}
case 6:
{
printf("
So nut co tren do thi la %d", SoNut);
break;
}
case 7:
{
printf("
Cac cung co tren do thi:
");
for(i = 0; i < SoNut; i++)
for(j = 0; j < SoNut; j++)
if((weight[i][j] > 0) && (weight[i][j] < VOCUNG))
printf(" %d%s%d : %d
", i, " -> ", j, weight[i][j]);
break;
}
case 8:
{
printf("
Nhap cung can tim: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut)
printf("Khong hop le");
else
if((weight[x][y] > 0) && (weight[x][y] < VOCUNG))
printf("Co cung voi trong so %d", weight[x][y]);
else
printf("Khong co cung nay");
break;
}
case 9:
{
printf("
Nhap nut di va nut den: ");
scanf("%d %d", &x, &y);
if(x >= SoNut || y >= SoNut)
printf("Khong hop le");
else
{
floyd();
printf("Chieu dai ngan nhat tu %d den %d la %d", x, y, D[x][y]);
printf("
Duong di la: ");
inlotrinh(x, y);
}
break;
}
}
} while(chucnang != 0);
}
Bài liên quan
