Tìm đường đi ngắn nhất = thuật toán Dijsktra

Ở đây Gió xin trình bày phương pháp Dijkstra cho đồ thị có các trọng số không âm. Thuật toán này được xây dựng trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ đỉnh start đến đỉnh đó. Đỉnh start ở đây chúng ta hiểu là đỉnh nguồn, đỉnh finish là đỉnh đích. Các nhãn này được biến đổi theo thủ tục lặp, mà ở mỗi bước lặp có một nhãn tạm thời trở thành nhãn cố định, một nhãn tạm thời trở thành nhãn cố định khi nó là đỉnh liền kề gần nhất với đỉnh đang được đưa vào xét. Nếu nhãn nào đó trở thành nhãn cố định thì nó cho ta giá trị độ dài của đường đi ngắn nhất từ đỉnh start đến đỉnh đó.

Đầu vào của chúng ta ở đây là ma trận trọng số không âm, hai đỉnh start và finish, và đầu ra sẽ là khoảng cách giữa hai đỉnh vừa được nhập vào này. Lưu ý rằng trước khi thực hiện thuật toán này chúng ta cần khởi gán lại các giá trị của các đỉnh của đồ thị như sau: Nếu đỉnh “start” nhập vào có lân cận với đỉnh “v” thì đỉnh “v” này được gán một nhãn tạm thời có  giá trị bằng khoảng cách từ đỉnh start đến đỉnh “v” này. Còn ngược lại nếu không có quan hệ lân cận thì nó sẽ nhận một giá trị vô cùng lớn, nhưng trong bài toán cụ thể chúng ta chọn cho nó một số lớn khoảng cỡ bằng 99 là được rồi. Vì với mô hình cụ thể như thế này các cạnh có trọng số không lớn lắm.

Thuật toán như sau:

void DuongDiNganNhat(const char*nameFile){
int D[20],P[20];
int start,finish;
int d = 0;     //cua mang P
int max = 99;
bool flag = false;
cout<<“\nDinh nguon la: “;
cin>>start;
while(cin.fail()||start>=soDinh){
cout<<“\nError: du lieu cua dinh nguon bi sai”;
cout<<“\nLuu y dinh nhap vao la so ‘integer’ va nho hon “<<soDinh<<“. Nhap lai: “;
cin.clear();
cin.ignore();
cin>>start;
}
cout<<“\nDinh dich la: “;
cin>>finish;
while(cin.fail()||finish>=soDinh||finish==start){
cout<<“\nError: du lieu cua dinh ket thuc bi sai!”;
cout<<“\nLuu y dinh nhap vao la so ‘integer’, phai khac dinh ‘nguon’ va nho hon “<<soDinh;
cout<<“\nNhap lai: “;
cin.clear();
cin.ignore();
cin>>finish;
}
was_visited[start] = true;
int a = start;
D[a] = 0;
P[0] = start;
//khoi tao cac gia tri cho hai mang D chua do dai
for(int i=0;i<soDinh;i++){
if(A[i][a]==0&&i!=a)
D[i] = 99;
else
D[i] = A[i][a];
}
while(true){
int u = -1;
//tim mot dinh chua duoc tham  va la lien ke roi gan no lam mo^’c
for(int i = 0;i<soDinh;i++)
if(was_visited[i]==false && A[a][i]!=0){
max = A[a][i];
u    = i;
break;
}
//tim dinh lien ke gan nhat chua duoc tham cua dinh a(la dinh dang duoc dua vao P[]
for(int i=0;i<soDinh;i++)
if(was_visited[i]==false && A[a][i]!=0 && max>A[a][i]){
max    =    A[a][i];
u    =    i;
}
was_visited[u] = true;
// neu dinh lien_ke_gan_nhat duoc chon chinh la dinh finish
// hoac khong xac dinh duoc gia tri cua lin_ke_gan_nhat thi deu thoat khoi
vong lap
if(u == -1 || u == finish){
d++;
P[d] = finish;
break;
}
//v la dinh lien ke gan nhat cua u D[v] se duoc gan gia tri co dinh
for(int v = 0; v < soDinh; v++){
if(D[v]>D[u]+A[u][v] && A[v][u]!=0 && was_visited[v]==false){
D[v] =    D[u] + A[u][v];
if(u!=P[d]){    //tranh viec lap lai du lieu
d++;
P[d]    =    u;
}
if(v==finish){ //neu da la dinh finish ket thuc luon o day
d++;
P[d] = finish;
flag = true;
break;
}
}
if(D[v]>D[finish] && A[u][v]!=0){
d++;
P[d] = finish;
}

}
if(flag)
break;
a = u;     //dinh tiep theo bi do xet la dinh lien ke gan nhat
}
cout<<“\nKet qua se duoc nghi tren file\n”;
//———-ghi ket qua len file———
ofstream dataFile(nameFile);
if(!dataFile.fail()){
if(D[finish] == 99)
dataFile<< “khong co duong di tu ” << start << ” den ” << finish << endl;
else{
dataFile<<“gia tri khoang cach duong di ngan nhat la : “<<D[finish]<<“\n”;
dataFile<<“duong di tu “<<start<<” den “<<finish<<” la : “<<“\n”;
dataFile<<start;
for(int l=1;l<=d;l++)
dataFile<<“–>”<<P[l];
}
}

}

5 thoughts on “Tìm đường đi ngắn nhất = thuật toán Dijsktra

  1. adim ơi cho em hỏi tìm đường đi ngắn nhất trên đồ thị có hướng giống vậy không?
    cho em xin bản full ây?
    thank nhiều
    send mail dùm:ng_quang_sangpro@yahoo.com.vn

  2. Xin lỗi bạn vì bài viết đã rất lâu rồi và giờ cuộc sống của tôi đã thay đổi nhiều ko còn cơ hội làm việc với các vấn đề này nên ko thể trả lời bạn đc. Có điều mong bạn đừng từ bỏ vấn đề của mình mà hãy tìm kiếm chúng ở những nguồn khác.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s