Tìm kiếm đường đi ngắn nhất trên đồ thị (Dijikstra)

Trong bài học trước, chúng ta đã tìm hiểu về thuật toán Floyd-Warshall trong việc tìm kiếm đường đi ngắn nhất trên đồ thị. Hôm nay, chúng ta sẽ tìm hiểu về một thuật toán phổ biến khác trong tìm kiếm đường đi ngắn nhất. Hãy cùng bắt đầu!

Tìm hiểu về thuật toán Dijkstra

Bài toán đặt ra

Ta đặt một bài toán như sau: Cho một đồ thị có hướng gồm đỉnh và cạnh có hướng và trọng số không âm. Cho một đỉnh , hãy tìm độ dài đường đi ngắn nhất từ đỉnh đến tất cả các đỉnh còn lại. Nếu không tồn tại đường đi giữa hai đỉnh, in ra -1.

Bạn đang xem: Tìm kiếm đường đi ngắn nhất trên đồ thị (Dijikstra)

Ý tưởng

Ý tưởng của thuật toán Dijkstra giống với thuật toán Floyd-Warshall. Với mỗi cạnh nối hai đỉnh và , ta so sánh độ dài đường đi trước đây với đường đi mới.

Xem thêm : Bộ câu hỏi trắc nghiệm An toàn giao thông cho học sinh Tiểu học Đề trắc nghiệm an toàn giao thông cho học sinh Tiểu học

Tại mỗi bước, ta chọn một đỉnh mà ta biết chắc chắn đường đi từ là đường đi ngắn nhất. Sau đó, ta xét tất cả các đỉnh mà có cạnh liên kết trực tiếp và tối ưu đường đi dựa trên đường đi hiện tại.

Cách cài đặt

Trước hết, để thể hiện một cạnh, ta sử dụng vector với kiểu dữ liệu pair. Mỗi pair là một cấu trúc cho phép lưu trữ hai phần tử. Ta có thể truy cập vào hai phần tử của pair thông qua hai phương thức first và second.

Ví dụ:

#include
using namespace std;
int main(){
    pair myPair[2]; // Có 2 cách khởi tạo pair
    myPair[0] = make_pair(1, 2);
    myPair[1] = {2, 3};
    cout << myPair[0].first << " " << myPair[0].second << endl; // Kết quả: 1 2
    return 0;
}

Xem thêm : Let Off là gì và cấu trúc cụm từ Let Off trong câu Tiếng Anh

Ta sẽ cần khởi tạo hai mảng với ý nghĩa như sau:

• dist[u] : độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Ban đầu dist[u] = ∞ với mọi u, riêng dist[s] = 0
• mark[u] : đánh dấu đỉnh u đã được xét hay chưa. Ban đầu các phần tử trong mảng có giá trị false.

==> Trong ví dụ trên, ta thấy có tối đa nên độ dài một đường đi không quá , khi này có thể là bất cứ giá trị nào lớn hơn hoặc bằng

Minh hoạ
Mình sẽ minh họa thuật toán bằng một đồ thị cơ bản sau với đỉnh nguồn là đỉnh 1:

• Đầu tiên, dist = [0, ∞, ∞, ∞] và mark = [0, 0, 0, 0] (ta coi 0 là false và 1 là true).
• Ta chọn u = 1 do dist[1] = 0 nhỏ nhất và thoả mãn mark[1] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 1.
  • Xét v = 2, ta thấy dist[1] + độ dài cạnh (1, 2) = 3 < dist[2] = ∞ nên dist[2] = 3
  • Xét v = 3, ta thấy dist[1] + độ dài cạnh (1, 3) = 6 < dist[3] = ∞ nên dist[3] = 6
• Do không còn đỉnh nối từ đỉnh 1 nên ta kết thúc xét đỉnh 1 và đánh dấu mark[1] = 1
• Khi này, dist = [0, 3, 6, ∞] và mark = [1, 0, 0, 0]
• Ta chọn u = 2 do dist[2] = 3 nhỏ nhất và thoả mãn mark[2] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 2.
  • Xét v = 3, ta thấy dist[2] + độ dài cạnh (2, 3) = 4 < dist[3] = 6 nên dist[3] = 4
  • Xét v = 4, ta thấy dist[2] + độ dài cạnh (2, 4) = 10 < dist[4] = ∞ nên dist[4] = 10
• Do không còn đỉnh nối từ đỉnh 2 nên ta kết thúc xét đỉnh 2 và đánh dấu mark[2] = 1
• Khi này, dist = [0, 3, 4, 10] và mark = [1, 1, 0, 0]
• Ta chọn u = 3 do dist[3] = 4 nhỏ nhất và thoả mãn mark[3] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 3.
  • Xét v = 4, ta thấy dist[3] + độ dài cạnh (3, 4) = 8 < dist[4] = 10 nên dist[4] = 8
• Do không còn đỉnh nối từ đỉnh 3 nên ta kết thúc xét đỉnh 3 và đánh dấu mark[3] = 1
• Khi này, dist = [0, 3, 4, 8] và mark = [1, 1, 1, 0]
• Ta chọn u = 4 do dist[4] = 0 nhỏ nhất và thoả mãn mark[4] = 0. Xét các đỉnh v có cạnh nối trực tiếp từ đỉnh 4.
• Do tất cả các đỉnh đã được đánh dấu nên thuật toán kết thúc và ta thu được dist = [0, 3, 4, 8]

Minh hoạ để mô phỏng thuật toán Dijkstra và giải thích từng bước của thuật toán

Code cơ bản

#include
using namespace std;
typedef long long ll;
const int MaxN = 1 + 1e2;
const ll INF = 1e18;
int n, m, s;
bool mark[MaxN];
ll dist[MaxN];
vector> adj[MaxN];

void Dijkstra(int s){
    fill(dist + 1, dist + n + 1, INF);
    dist[s] = 0;
    for(int i = 1 ; i <= n ; ++i){
        int v = -1;
        for(int j = 1 ; j <= n ; ++j){
            if(!mark[j] && (v == -1 || dist[j] < dist[v]))
                v = j;
        }
        if(v == -1) 
            break;
        mark[v] = 1;
        for(auto u : adj[v]){
            if(mark[u.first]) 
                continue;
            dist[u.first] = min(dist[u.first], dist[v] + u.second);
        }
    }
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> m >> s;
    for(int i = 0 ; i < m ; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    Dijkstra(s);
    for(int i = 1 ; i <= n ; ++i){
        if(dist[i] == INF) 
            cout << -1 << endl;
        else 
            cout << dist[i] << endl;
    }
    return 0;
}

Độ phức tạp
Độ phức tạp của thuật toán Dijkstra là O(V^2), trong đó V là số lượng đỉnh trong đồ thị. Mỗi vòng lặp sẽ chỉ mất O(V) thời gian, và có V vòng lặp. Tuy nhiên, nếu ta sử dụng cấu trúc dữ liệu heap như priority_queue, độ phức tạp sẽ giảm xuống O((V + E)logV), trong đó E là số lượng cạnh trong đồ thị.

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập