[Thuật toán đồ thị / code C++] Thuật toán Dijkstra - tìm đường đi ngắn nhất từ đỉnh D đến đỉnh C trên đồ thị G.

in , , , /

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 (tìm hiểu thêm về thuật toán Dijkstra tại đây).

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 Dijkstra.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.




[Cài đặt thuật toán với Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100
#define FileIn "Dijkstra.inp"

// doc file chua do thi G
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--;
 }

// thuat toan Dijkstra
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;
  }
 }
// ham chinh
void main() {
   int A[max][max],n,Dau,Cuoi; // ma tan A chua do thi
   Doc_File(A,n,Dau,Cuoi);
   Dijkstra(A,n,Dau,Cuoi);
   getch();
}