Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất
Có n thành phố biết rằng đường đi giữa các thành phố (nếu có) là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A[i,j] trong đó:
- A[i,j] là độ dài đường đi từ thành phố i đến thành phố j.
- A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
- A[i,j] = A[j,i]
- A[i,j] nguyên, không âm.
Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C.
Dữ liệu vào: đồ thị đã liên thông và cho trong file Bai7.inp với nội dung
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0
- Dòng i+2 (0Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.
Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 5
1 6 1->2->4->6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0
Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 8
1 6 1->2->4->6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0
Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileIn "Bai7.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int**A, int &n, int &D, int &C){
FILE*f = fopen(FileIn,"rb");
fscanf(f,"%d%d%d",&n,&D,&C);
cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
*A = new int [n];
for(int i =0;i<n;i++) {
A[i] = new int [n];
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl;
}
fclose(f);
D--; C--;
}
/*Thuật toán Dijkstra tìm đường đi ngắn nhẩt từ đỉnh D đến đỉnh C*/
void Dijkstra(int **A, int n, int D, int C) {
char *DanhDau = new char[n];
int *Nhan = new int[n];
int *Truoc = new int[n];
int XP, min;
for(int i=0; i<n; i++){
Nhan[i] = MAXINT;
DanhDau[i] = 0;
Truoc[i] = D;
}
Nhan[D] = 0;
DanhDau[D] = 1;
XP = D;
while(XP != C){
for(int j=0; j<n; j++)
if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
Nhan[j] = A[XP][j]+Nhan[XP];
Truoc[j] = XP;
}
min = MAXINT;
for(j = 0; j<n; j++)
if(min>Nhan[j]&& DanhDau[j]==0){
min = Nhan[j] ;
XP = j ;
}
DanhDau[XP] = 1;
}
cout<<”Duong Di Ngan Nhat La:”<<Nhan[C]<<endl;
cout<<C+1<<” <- “<<Truoc[C]+1;
i = Truoc[C];
while(i!=D){
i = Truoc[i];
cout<<” <- “<<i+1;
}
}
/*Chương trình chính*/
void main() {
int**A,n,Dau,Cuoi;
Doc_File(A,n,Dau,Cuoi);
Dijkstra(A,n,Dau,Cuoi);
delete*A;
getch();
}
Được sửa bởi admin ngày Thu Oct 04, 2012 1:50 pm; sửa lần 1.