Ngồi mò hồi ra một đóng tư liệu cấu trúc giải thuật. nhớ ngày xưa(gần 10 năm) mua cuốn sách trong cuốn sách có link down mã tham khảo
Thấy một số bạn khó khăn về mộtt số thuật toán, mã giải, mình post lên đây, xem như làm tư liệu tham khảo, Tác giả là Nguyễn Hồng Chương nhé. sách thì mất chỉ còn source. Nói trước là tham khảo, đọc và hãy hiểu nó nhé.
/*****************************************************************************
* Chuong trinh C10-1: Chuong trinh minh hoa giai thuat Dijkstra 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] = 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];
int SoNut; // so nut thuc su co tren do thi
// 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++)
weight[i][j] = VOCUNG;
}
// Tac vu joinwt: them mot cung moi tu node1 den node2 co trong so wt
void joinwt(int node1, int node2, int wt)
{
weight[node1][node2] = wt;
}
// Tac vu remvwt: xoa mot cung tu node1 den node2
void remvwt(int node1, int node2)
{
weight[node1][node2] = VOCUNG;
}
/* Tac vu dijkstra: tim duong di ngan nhat tren do thi co trong so theo
giai thuat Dijkstra.
Du lieu nhap:
s: nut di, t: nut den
Du lieu xuat:
ngan1: chieu dai duong di ngan nhat tu s den t
duongdi[]: mang ghi nhan lo trinh ngan nhat tu s den t, luu y
duongdi[i] la nut truoc nut i tren lo trinh ngan nhat */
void dijkstra(int s, int t, int *ngan1, int duongdi[])
{
int i, k, kc, nuthientai, min, kcachmoi;
int tapcacnut[TOIDA]; // tap cac nut da xet
int kcach[TOIDA]; /* mang luu chieu dai duong di ngan nhat tu nut
s den cac nut khac */
// Buoc 0: khoi dong mang tapcacnut[] va kcach[]
for(i = 0; i < SoNut; i++)
{
tapcacnut[i] = FALSE;
kcach[i] = VOCUNG;
}
// dua nut s vao tap nut da xet
tapcacnut[s] = TRUE;
kcach[s] = 0;
nuthientai = s;
/* vong lap thuc hien cac buoc 1, 2, ... cho den khi dua duoc nut t vao
tap nut da xet */
while(nuthientai != t)
{
min = VOCUNG;
kc = kcach[nuthientai]; /* kc chieu dai duong di ngan nhat tu nut s
den nuthientai */
for(i = 0; i < SoNut; i++)
if(tapcacnut[i] == FALSE)
{
kcachmoi = kc + weight[nuthientai][i];
if(kcachmoi < kcach[i])
{
kcach[i] = kcachmoi;
duongdi[i] = nuthientai; /* gan nuthientai la nut truoc
nut i tren lo trinh */
}
if(kcach[i] < min)
{
min = kcach[i];
k = i;
}
}
// Dua nut k vao tap nut da xet
nuthientai = k;
tapcacnut[nuthientai] = TRUE;
}
*ngan1 = kcach[t];
}
// Chuong trinh chinh
void main()
{
int chon, x, y, i, j;
char c;
int wt, ngan1;
int duongdi[TOIDA];
int s, t;
clrscr();
initialize();
SoNut = 0;
do
{
printf("\n\n\tCHUONG TRINH TIM DUONG DI NGAN NHAT - GIAI THUAT DIJKSTRA");
printf("\n\nCac chuc nang cua chuong trinh:\n");
printf("\n1: Tao do thi moi");
printf("\n2: Them mot nut");
printf("\n3: Them mot cung");
printf("\n4: Xoa mot cung");
printf("\n5: Xoa toan bo do thi");
printf("\n6: Xac dinh so nut co tren do thi");
printf("\n7: Duyet cac cung");
printf("\n8: Tim cung");
printf("\n9: Tim duong di ngan nhat");
printf("\n0: Thoat");
printf("\nChon chuc nang: ");
scanf("%d", &chon);
switch(chon)
{
case 1:
{
initialize();
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", &wt);
weight[x][y] = wt;
}
};
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)
printf("Khong hop le");
else
{
printf("Trong so cua cung %d -> %d : ", x, y);
scanf("%d", &wt);
joinwt(x, y, wt);
}
break;
}
case 4:
{
printf("\nNhap cung can xoa: ");
scanf("%d %d", &x, &y);
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] < 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] < VOCUNG)
printf("Co cung voi trong so %d", weight[x][y]);
else
printf("Khong co cung nay");
break;
}
case 9:
{
printf("\nNhap nut di: ");
scanf("%d", &s);
printf("\nNhap nut den: ");
scanf("%d", &t);
dijkstra(s, t, &ngan1, duongdi);
printf("\nDuong di ngan nhat tu %d->%d la: %d ", s, t, ngan1);
printf("\nLo trinh: ");
i = t;
while(i != s)
{
printf("%d <- ", i);
i = duongdi[i];
}
printf("%d", s);
break;
}
}
} while(chon != 0);
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?