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("\n\n\t\tGRAPH - GIAI THUAT FLOYD TIM DUONG DI NGAN NHAT");
printf("\n\nCac chuc nang cua chuong trinh:\n");
printf(" 1: Tao do thi moi\n");
printf(" 2: Them mot nut\n");
printf(" 3: Them mot cung\n");
printf(" 4: Xoa mot cung\n");
printf(" 5: Xoa toan bo do thi\n");
printf(" 6: Xac dinh so nut co tren do thi\n");
printf(" 7: Duyet cac cung\n");
printf(" 8: Tim cung\n");
printf(" 9: Tim duong di ngan nhat (giai thuat Floyd)\n");
printf(" 0: Ket thuc chuong trinh\n");
printf("Chuc nang ban chon: ");
scanf("%d", &chucnang);
switch(chucnang)
{
case 1:
{
initialize();
SoNut = 0;
printf("\nDo thi moi co bao nhieu nut: ");
scanf("%d", &SoNut);
printf("\Hay nhap cac cung cua do thi (nhap %d %d de ket thuc):\n",
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("\nNhap 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("\nNhap 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("\nBan co chac khong (c/k): ");
c = getche();
if(c == 'c' || c == 'C')
{
initialize();
SoNut = 0;
}
break;
}
case 6:
{
printf("\nSo nut co tren do thi la %d", SoNut);
break;
}
case 7:
{
printf("\nCac cung co tren do thi:\n");
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\n", i, " -> ", j, weight[i][j]);
break;
}
case 8:
{
printf("\nNhap 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("\nNhap 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("\nDuong di la: ");
inlotrinh(x, y);
}
break;
}
}
} while(chucnang != 0);
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?