Code C/C++: Thuật toán Dijkstra tìm đường đi ngắn nhất

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G.
Ý tưởng thuật toán: sử dụng thuật toán Dijkstra.
Mô tả dữ liệu đầu vào và đầu ra của bài toán:
Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Bai6.inp. 
-  Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
-  Dòng thứ hai lưu đỉnh D và đỉnh C.
-  Dòng i+2 (1<=i<=n) chứa n số A[i,1], A[i,2],…, A[i,n] mỗi số cách nhau bởi một khoảng trắng.
Dữ 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.
Ví dụ:

Cài đặt chương trình:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Bai6.inp"
void Doc_File(int A[max][max], 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";
cout<<D<<" "<<C<<endl;
for(int i =0;i<n;i++) {
for(int j =0;j<n;j++) {
fscanf(f,"%d",&A[i][j]);
cout<<A[i][j]<<" ";
}
cout<<endl; 
}
fclose(f);
D--; C--;
}
void Dijkstra(int A[max][max], int n, int D, int C) {
char DanhDau[max];
int Nhan[max], Truoc[max], 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;
}
}
void main() {
int A[max][max],n,Dau,Cuoi;



Doc_File(A,n,Dau,Cuoi);
Dijkstra(A,n,Dau,Cuoi);
getch();

} 
Kết quả chạy chương trình:

Tags: kỹ thuật lập trình, c, c++, toán rời rạc, đồ thị, tìm đường đi, Dijkstra.