Thuật toán Dijkstra

    Hôm nay chúng ta sẽ đi giải quyết thuật toán Dijkstra, một thuật toán được ứng dụng rất nhiều trong định tuyến (mạng, bản đồ, ...). Thuật toán giúp chúng ta tìm đường đi ngắn nhất từ một nút (đỉnh) tới tất cả các nút (đỉnh) còn lại trong đồ thị trọng số không âm.

Ta sẽ đi triển khai thuật toán luôn nhé!

1. Triển khai thuật toán

#include<iostream>
#include<vector>
using namespace std;

#define INF 1e9

vector<int> Dijkstra(vector<vector<int>> G, int n, int s){ //gốc là đỉnh s, n là số đỉnh
  //Khởi tạo
  vector<int> p(n, s); // p[i] = j thì j là đỉnh cha của đỉnh i
  vector<int> d(n, INF); // vector d là nhãn của từng đỉnh
  vector<bool> k(n, false); // vector k thể hiện trạng thái đã xét của mỗi đỉnh 
  d[s] = 0;
  int count = 1;

  while(count < n){
    // Tìm đỉnh có nhãn nhỏ nhất trong tập đỉnh chưa được xét
    int mind = INF, u;
    for(int i = 0; i < n; i++){
      if(!k[i] && d[i] < mind){
        mind = d[i];
        u = i;
      }
    } 
    k[u] = true; //Thêm đỉnh u vào tập đỉnh đã được xét
    
    for(int v = 0; v < n; v++){
        if(!k[v] && d[u] + G[u][v] < d[v]){
          d[v] = d[u] + G[u][v]; //cập nhật lại đỉnh v
          p[v] = u;
        }
    }
    count++;
  }
  return p;
}

int main(){
  int n, edges; //số đỉnh, số cạnh
  cin >> n >> edges;

  int u, v, w;
  vector<vector<int>> G(n, vector<int>(n, INF));
  for(int i = 0; i < edges; i++){
    cin >> u >> v >> w;
    G[u][v] = w;
    G[v][u] = w;
  }

  // for(int i = 0; i < n; i++){
  //   for(int j = 0; j < n; j++)
  //     cout << G[i][j] << '\t';
  //   cout << endl;
  // }

  vector<int> p = Dijkstra(G, n, 0);

  for(int i = 0; i < n; i++)
    cout << p[i] << " -> " << i << endl;

  return 0;
}

2. Sử dụng hàng đợi ưu tiên (Priority Queue)

    Sử dụng hàng đợi ưu tiên (priority queue) giúp giảm độ phức tạp thời gian của thuật toán, bản chất ta sẽ thay quá trình tìm đỉnh có nhãn nhỏ nhất trong tập đỉnh chưa được xét bằng một cái hàng đợi ưu tiên min.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define INF 1e9

typedef pair<int, int> iPair; // pair<nhãn, đỉnh>

vector<int> DijkstraPQ(vector<vector<int>> G, int n, int s){
  //Khởi tạo
  priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
  vector<int> p(n, s); 
  vector<int> d(n, INF); // d là nhãn của từng đỉnh
  vector<bool> k(n, false); // k[i] = true thì i đã được thêm vào cây 
  d[s] = 0;
  for(int i = 0; i < n; i++)
    pq.push(make_pair(d[i], i));

  while(!pq.empty()){
    // Tìm đỉnh có nhãn nhỏ nhất trong tập đỉnh chưa được xét
    int u = pq.top().second;
    pq.pop();
    k[u] = true; //Thêm đỉnh u vào cây
    
    for(int v = 0; v < n; v++){
        if(!k[v] && d[u] + G[u][v] < d[v]){
          d[v] = d[u] + G[u][v]; //cập nhật lại đỉnh v
          pq.push(make_pair(d[v], v));
          p[v] = u;
        }
    }
  }
  return p;
} 

int main(){
  int n, edges; //số đỉnh, số cạnh
  cin >> n >> edges;

  int u, v, w;
  vector<vector<int>> G(n, vector<int>(n, INF));
  for(int i = 0; i < edges; i++){
    cin >> u >> v >> w;
    G[u][v] = w;
    G[v][u] = w;
  }

  // for(int i = 0; i < n; i++){
  //   for(int j = 0; j < n; j++)
  //     cout << G[i][j] << '\t';
  //   cout << endl;
  // }

  vector<int> p = DijkstraPQ(G, n, 0);

  for(int i = 0; i < n; i++)
    cout << p[i] << " -> " << i << endl;

  return 0;
}

Ok, vậy là ổn rồi nhỉ. Hẹn gặp lại mọi người ở bài viết tiếp theo.