dijkstra.cpp

Dijkstra by C is so great for solving algorithm find the shortest path with weigth!

/*****************************************************
*Chuong trinh minh hoa giai thuat Dijkstra tim duong di *
* ngan nhat tren do thi co trong so *
******************************************************/

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