Chương trình minh họa giải thuật Dijkstra tìm đường đi ngắn nhất

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("

	CHUONG TRINH TIM DUONG DI NGAN NHAT - GIAI THUAT DIJKSTRA");
		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");
		printf("
0: Thoat");
		printf("
Chon chuc nang: ");
		scanf("%d", &chon);
		switch(chon)
		{
			case 1:
			{
				initialize();
				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", &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("
Nhap 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("
Nhap cung can xoa: ");
				scanf("%d %d", &x, &y);
				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] < 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] < VOCUNG)
						printf("Co cung voi trong so %d", weight[x][y]);
					else
						printf("Khong co cung nay");
				break;
			}
			case 9:
			{
				printf("
Nhap nut di: ");
				scanf("%d", &s);
				printf("
Nhap nut den: ");
				scanf("%d", &t);
				dijkstra(s, t, &ngan1, duongdi);
				printf("
Duong di ngan nhat tu %d->%d la: %d ", s, t, ngan1);
				printf("
Lo trinh: ");
				i = t;
				while(i != s)
				{
					printf("%d <- ", i);
               i = duongdi[i];
				}
				printf("%d", s);
				break;
			}
		}
	} while(chon != 0);
}