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

Thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị G

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 InputDijkstra.txt.
 - 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 bài toán - code C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100

void Doc_File(int A[max][max], int &n, int &D, int &C) {
   FILE*f = fopen("InputDijkstra.txt","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;
      }
}

void main() {
    int A[max][max],n,Dau,Cuoi;
    Doc_File(A,n,Dau,Cuoi);
    Dijkstra(A,n,Dau,Cuoi);
     getch();
}

/***** LƯU Ý ****/
File Input.txt được đặt ở thư mục chứa code , các bạn có thể tạo phải Input.txt khác tùy vào đồ thị mà bạn muốn kiểm tra


Chúc các bạn thành công!


2 nhận xét:

  1. Cho em hỏi trong thuật toán có sử dụng biên MAXINT mà ko khai báo, vậy biến MAXINT đó là gì ạ?

    Trả lờiXóa
  2. MAXINT là số nguyên lớn nhất.

    Trả lờiXóa

Cảm ơn bạn đã quan tâm tới bài viết này!