Thuật toán Dijkstra và cài đặt

Lúc xưa, xưa dữ lắm xưa có học một ông thầy ông truyền thụ cho cách giải thuật toán Dijkstra bằng ngôn ngữ C tuy nhiên chẳng hỉu gì hết thôi kệ post bài này lên để mọi người cùng góp ý.

Thuật toán Dijkstra là gì?

Nghe thiên hạ đồn là thuật toán này do ông Edsger Dijkstra người Hà Lan tìm ra, giả thuyết cho ra là: Cho một đồ thị có hướng tức là một đồ thị có hương đi các cung nhất định, một trọng số và một nguồn nào đó. Vấn đề là phải tìm ra đường đi ngắn nhất từ nguồn đó đến các đỉnh còn lại.

Thuật toán Dijkstra

Thuật toán Dijkstra

Ký hiệu dùng trong giải thuật Dijkstra
  • Tập đỉnh đã được sắp thứ tự 0… n-1 , (có n đỉnh), với s là đỉnh gốc.
  • Ma trận kề A=[i,j]  giá trị của phần tử a[i][j] là độ dài từ i->j , [Vậy nếu a[i][j]=0, giữa i và j không có cạnh nối nhau].
  • Mark[i] = 1 : đã chọn (đỉnh i đã được chọn vào cây T), Mark[i]=0: ngược lại, [Mark là mảng có n phần tử dùng để đánh dấu một đỉnh i đã được chọn vào cây T hay chưa]
  • pr[i]: đỉnh trước đỉnh i (ví dụ: pr[6]=3, đỉnh 3 là đỉnh trước khi tới đỉnh 6), [pr : (previous) là mảng có n phần tử dùng để truy tìm ngược lại đỉnh trước(đỉnh cha) của một đỉnh nào đó]
  • d[i]: giá trị của phần tử d[i] là độ dài đường đi nối từ s->i (s là đỉnh gốc), [d là mảng có n phần tử, giá trị của phần tử thứ i chính là độ dài của s->i]
Ý tưởng giải Dijkstra
  • Ta sẽ xây dựng một cây phủ tối tiểu T từ một đỉnh s là đỉnh gốc của cây.
  • Ở mỗi bước lặp: chọn một đỉnh i ở ngoài cây T, sao cho đỉnh này nối được với cây, mà có đường đi tới gốc s là ngắn nhất. Dừng lặp khi T đã đủ n đỉnh.
  • Vậy kết quả là cây T cuối cùng là cây phủ, có đỉnh gốc là s đi tới các đỉnh còn lại bất kỳ là ngắn nhất.

Thủ tục
Khởi tạo:

  • Gốc s; d=vocuc; d[s]=0
  • Mark=0;  
  • Mark[s]=1;   [chọn s là một đỉnh trong cây T, (s là đỉnh gốc)]
  • d=a[s][i];  [lưu lại độ dài từ s đến tất cả đỉnh i (lấy ra được từ ma trận kề) vào mảng d]
  • pr[i]=s;   [đỉnh s là đỉnh trước(đỉnh cha) của tất cả các đỉnh còn lại]

Ở mỗi bước lặp trong thuật toán Dijkstra
1) Tìm k: d[k] = min {d[j]: Mark[j] =0 },  [k là đỉnh được chọn từ tất cả các đỉnh j nằm ngoài cây T (tức là Mark[j]=0), sao cho khoảng cách từ s->k (tức là d[k]) là nhỏ nhất so với các khoảng cách từ s->j (tức là d[j]) ]
2) Cập nhật:

  • Mark[k] = 1;
  • Với mọi đỉnh j mà Mark[j]=0
  • Nếu d[k]+a[k][j] < d[j] thì
  • d[j] = d[k]+a[k][j];
  • pr[j] = k;

Giải thích phần cập nhật:

  • Mark[k] = 1, [chọn đỉnh k vào cây T]
  • Mark[j]=0, [chỉ chọn đỉnh j chưa được đánh dấu (còn nằm ngoài cây T)]
  • d[k]+a[k][j] < d[j], [nếu khoảng cách từ s->j (tức là d[j]) mà lớn hơn khoảng cách từ s->k->j (tức là d[k]+a[k][j] ) thì chọn lại đường đi ngắn nhất từ s->j sẽ đi qua k (s->j->k)]
  • d[j] = d[k]+a[k][j], [độ dài từ s->j (tức là d[j]) bằng với độ dài từ s->k (tức là d[k]) và từ k->j (tức là a[k][j]).]
  • pr[j]=k, [đỉnh k là đỉnh trước khi tới j]
Cài đặt hoàn chỉnh Dijkstra
<!--
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 10
#define vocuc 666

//prototype
int Doc_Dothi(char filename[], int [][MAX], int &);
void Xuat_Matran(int [][MAX], int);
int Dijkstra(int [][MAX],int,int );

void main(){
	int a[MAX][MAX],n,s;
	char duongdan[30],kt; 

	while (1){
	printf("Cho biet duong dan cua do thi bieu dien: ");
	scanf("%s",duongdan);
	
	if (Doc_Dothi(duongdan,a,n)){
		Xuat_Matran(a,n);
		printf("Ban hay chon dinh goc: ");
		scanf("%d",&s);
		if (Dijkstra(a,n,s)==0)
			printf("Do thi xuat phat tu %d khong lien thong !",s);
	}	
	printf("\nBan co muon tiep tuc: nhan mot phim bat ky de tiep tuc!\n");
	printf("Nhan N or n de ket thuc!!!\n");
	scanf("%s",&kt);
	if (kt=='N' || kt=='n')
		break;
	printf("\n");
	}
	getch();		
}

//Ham doc do thi => tra ve 1: doc thanh cong, 0:doc that bai
int Doc_Dothi(char filename[], int a[MAX][MAX], int &n) {
	FILE *f;
	f=fopen(filename, "rt");
	if(f==NULL) {
		printf("Loi mo file !!!\n"); 
		printf("co the ban chon duong dan ko dung, vd: e:\\dothi.txt \n\n");
		return 0;  	//doc that bai
	}
	fscanf(f,"%d\n",&n);
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++)
			fscanf(f,"%d",&a[i][j]);
		fscanf(f,"\n");
	}
	fclose(f);
	return 1;		//doc thanh cong
}


//Ham xuat ma tran ke
void Xuat_Matran(int a[][MAX], int n) {
	printf("\n");
	for (int i=0;i<n;i++) {
		for (int j=0;j<n;j++)
			printf("%d\t",a[i][j]);
		printf("\n");
	}
	printf("\n");
}

//Ham tra ve 0: do thi khong lien thong, tra ve 1: lien thong, [s: dinh xuat phat, dinh goc]
int Dijkstra(int a[][MAX],int n,int s) {
	int Mark[MAX],d[MAX],pr[MAX], k,min,dem;
	
	//Khoi tao theo ly thuyet slide hoc cua cac ban 
	for(int i=0;i<n;i++){
		d[i]=vocuc;			//tu dinh goc s den cac dinh con lai la vocuc
		Mark[i]=0; 			//chua co dinh nao dc chon vao cay T
		pr[i]=s;			//s la dinh truoc khi den tat ca dinh i con lai
	}
	
	//khoi tao
	for(int j=0;j<n;j++) {
		if(a[s][j])		//neu co canh noi giua s va j
			d[j]=a[s][j];	//luu lai khoang cach tu s->j vao mang d [d la mang luu lai khoang cach tinh tu s]
	}
	
	d[s]=0;				//khoang cach s->s la 0  [d la mang luu lai khoang cach tinh tu s]
	Mark[s]=1; 			//s la dinh dau tien dua vao cay T
	
	dem=n-1;			//chuan bi lap n-1 lan, tuc chon n-1 dinh con lai vao cay T, [n-1: tru ra dinh s da dc chon roi]
	while (dem>0) {			//lan luot chon n-1 dinh dua vao cay T [co n dinh, tru ra dinh s da dua vao cay T truoc do roi]
		min = vocuc;   		
		for(int i=0;i<n;i++)			  //di tim dinh k, 
			if ((Mark[i]==0) && (d[i]<min)) { //ma k o ngoai cay T, sao cho d[k] la nho nhat
				min = d[i];
				k = i;
			}
		if (min==vocuc){
			printf("Do thi khong lien thong");
			return 0;
		}
		Mark[k]=1;	      //Chon dc k dua vao cay T
		for (int j=0;j<n;j++) //Cap nhat lai gia tri
			if ((Mark[j]==0) && (d[k]+a[k][j]<d[j]) && (a[k][j]>0)) {
				d[j]=d[k]+a[k][j];
				pr[j]=k;
			}
		dem--;
	}

	
	//In kq: dinh goc xp- > tat ca cac dinh con lai	
	for (int i=0;i<n;i++)
		if (i!=s)		//neu la dinh goc ==> khong in ra man hinh
			if(d[i]==vocuc)	//khong co duong di tu s->i
				printf("ko co duong di tu %d->%d\n",s,i);
			else {
				printf("duong di tu %d->%d co do dai la: %d . ",s,i,d[i]);
				printf("Cac dinh di qua la : ");
			 	int mang[MAX];
			 	dem=0;
			 	int tam=pr[i];
			 	while (tam!=s) {
			 		mang[dem]=tam;
			 		tam=pr[tam];
			 		dem++;
			 	}
			 	printf("%d->",s);
			 	for (int j=dem;j>0;j--)
			 		printf("%d->",mang[j-1]);
		 		printf("%d\n",i);
			}
	return 1;
}
-->

Kết luận: Dijkstra là một giải thuật được đánh giá là khó, mình mong các bạn góp ý nha! hii…
Download hoàn chỉnh bài hướng dẫn có file cài đặt và chương trình mình họa cho thuật toán Dijkstra: Dijkstra Download

VN:F [1.9.22_1171]
Rating: 9.1/10 (15 votes cast)
Thuật toán Dijkstra và cài đặt, 9.1 out of 10 based on 15 ratings
Share This