EnglishFrenchGermanItalianJapanesePortugueseRussianSpanishVietnamese
C/C++

Giải thuật dijkstra tìm đường đi ngắn nhất – Bài toán du lịch C++

Giải thuật dijkstra tìm đường đi ngắn nhất – Bài toán du lịch C++

Chào các bạn, hôm nay mình sẽ giải bài toán du lịch bằng giải thuật dijkstra bằng ngôn ngữ C++.

Đề bài: Một người đi từ thành phố 0 đến thành phố n và có thể đi qua n-1 thành phố khác. Giá vé đi từ thành phô i đến thành phố j là c[i][j]. Tìm lộ trình từ thành phố 0 đến thành phố n sao cho tổng chi phí của giá vé đạt được là tiêu cực nhất.

Dijkstra

Bài toán có thể được tổ chức thành đồ thị như hình trên. Mỗi điểm của đồ thị có thể xem như một thành phố. Hai thành phố có thể liên thông với nhau với một trọng số nhất định. Chúng ta sẽ cài đặt giải thuật sao cho đường đi từ Đỉnh 1 đến đỉnh 10 là ngắn nhất.

Cài đặt:

  • Đầu tiên chúng ta sẽ có một ma trận để lưu đồ thị cần duyệt:
#include <iostream>
#include <limits.h>

using namespace std;

//Xem moi thanh pho la mot diem tren ma tran. 
int mat[100][100] = 
{
    { 0, 0 , 20, 0, 0, 21, 19, 0, 0, 0},
    { 0, 0 , 0, 0, 0, 21, 19, 0, 8, 0},
    { 20, 0 , 0, 4, 5, 0, 0, 0, 0, 0},
    { 0, 0 , 4, 0, 0, 0, 4, 0, 0, 0},
    { 0, 0 , 5, 0, 0, 0, 0, 0, 0, 4},
    { 21, 21 , 0, 0, 0, 0, 2, 0, 0, 0},
    { 19, 19 , 0, 4, 0, 2, 0, 0, 0, 0},
    { 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0},
    { 0, 8 , 0, 0, 0, 0, 0, 0, 0, 3},
    { 0, 0 , 0, 0, 4, 0, 0, 0, 3, 0}
};

Hàm printPath để in ra kết quả.

Hàm dijkstra sẽ có input là đỉnh bắt đầu và đỉnh kết thúc.

Output sẽ là tổng trọng số và thứ tự duyệt qua từng đỉnh.

void dijkstra(int start, int finish)
{
  int back[100], weight[100], mark[100]; //Luu dinh, trong so va danh dau dinh. 
  
  //Khoi tao
  for(int i =0 ; i < 10; i++){
    back[i] = -1; 
    mark[i] = 0; 
    weight[i] = INT_MAX;
  }	
  
  //Bat dau tai dinh dau tien
  back[start] = 0;
  weight[start] = 0;
  
  //Kiem tra su lien thong giua 2 do thi
  int connect;
  do {
    //bat dau tai dinh 0 nen connect = -1
    connect = -1;
    int min = INT_MAX; 
    
    //Lan luot duyet qua tat ca cac dinh trong do thi
    for (int j = 0; j < n; j++)
      //Neu dinh chua duoc danh dau
      if (mark[j] == 0){
        //Neu ton tai duong di giua dinh start va dinh j
        //weight[j]: tong trong so tu dinh bat dau den dinh dang xet
        //weight[start] + mat[start][j]: trong so dang xet
        if (mat[start][j] != 0 &&
          weight[j] > weight[start] + mat[start][j]
        ){
          //Luu lai dung de so sanh lan sau
          weight[j] = weight[start] + mat[start][j];
          //luu dinh cha
          back[j] = start;
        }
        //Tim duong di ngan nhat hien tai
        if (min > weight[j]){
          min = weight[j];
          //Dua vao connect de quyet dinh dinh tiep theo can duyet 
          //va biet duoc do thi co lien thong hay khong
          connect = j;
        }
      }
      start = connect;
      mark[start] = 1;
  } while(connect != -1 && start != finish);
  // start != finish: dinh dau va dinh cuoi gap nhau
  // connect != -1: neu khong lien thong thi dung viec tim duong di ngan nhat
  
  cout<<"Trong so cua duong di la: " <<weight[finish] << endl;
  
  cout<<"Duong di ngan nhat la: ";
  printPath(0, finish, back);
  cout<<"NULL\n";
}

Cuối cùng chúng ta gọi hàm main để hoàn tất chương trình:

int main()
{
  //Duong di tu 0 -> 9
  dijkstra(0, 9);
  system("pause");
  return 0;
}

Như vậy là chúng ta đã giải thành công bài toán du lịch bằng giải thuật dijkstra. Cám ơn các bạn đã đọc bài viết.

 

Click to comment

Leave a Reply

Your email address will not be published. Required fields are marked *

To Top
Close