Đây là bài toán tìm đường đi ngắn nhất = thuật toán Dijsktra.
Ở đây mình 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];
}
}
}
Source nguồn: http://hahong.wordpress.com