Thuật toán Dijkstra

Chi Tiết Kỹ Thuật:

Thuật toán Dijkstra hoạt động bằng cách sử dụng một tập hợp các đỉnh đã biết khoảng cách ngắn nhất từ đỉnh nguồn và mở rộng dần tập hợp này cho đến khi tất cả các đỉnh đều đã được thăm. Các bước cơ bản của thuật toán bao gồm:

1. Khởi tạo khoảng cách từ đỉnh nguồn đến chính nó bằng 0 và đến tất cả các đỉnh khác bằng vô cùng.
2. Đặt tất cả các đỉnh vào một tập hợp chưa được thăm.
3. Chọn đỉnh có khoảng cách nhỏ nhất từ tập hợp chưa được thăm và cập nhật khoảng cách của các đỉnh lân cận.
4. Lặp lại bước 3 cho đến khi tất cả các đỉnh đã được thăm.

Pseudo-code của Thuật toán Dijkstra:

function Dijkstra(Graph, source):

    dist[source] ← 0  // Khởi tạo khoảng cách từ nguồn đến chính nó là 0

    for each vertex v in Graph:

        if v ≠ source:

            dist[v] ← infinity  // Khởi tạo khoảng cách đến tất cả các đỉnh khác là vô cực

        add v to Q  // Thêm tất cả các đỉnh vào hàng đợi ưu tiên Q

    while Q is not empty:

        u ← vertex in Q with min dist[u]  // Lấy đỉnh u trong Q có khoảng cách nhỏ nhất

        remove u from Q  // Loại bỏ u khỏi hàng đợi ưu tiên

        for each neighbor v of u:  // Duyệt qua từng đỉnh kề v của u

            alt ← dist[u] + length(u, v)  // Tính toán khoảng cách thay thế đến v thông qua u

            if alt < dist[v]:  // Nếu khoảng cách thay thế nhỏ hơn khoảng cách đã biết đến v

                dist[v] ← alt  // Cập nhật khoảng cách đến v với khoảng cách thay thế nhỏ hơn này

    return dist  // Trả về bảng khoảng cách từ nguồn đến từng đỉnh

Giải thích:

• alt là tổng khoảng cách từ nguồn đến đỉnh v thông qua đỉnh hiện tại u.
• dist[u] là khoảng cách ngắn nhất đã biết từ nguồn đến đỉnh hiện tại u.
• length(u, v) là khoảng cách từ đỉnh u đến đỉnh kề v.
• alt = dist[u] + length(u, v) tính toán tổng khoảng cách từ nguồn đến v nếu đi qua u.

Code C++:

// https://graphicmaths.com/computer-science/graph-theory/dijkstras-algorithm/

#include <bits/stdc++.h>

using namespace std;

#define V 5
#define INF INT_MAX

typedef pair<int, int> iPair;

// Mảng ánh xạ chỉ số đỉnh thành ký hiệu
char dinhKyHieu[V] = {'A', 'B', 'C', 'D', 'E'};

// Hàm in đường đi từ đỉnh nguồn đến một đỉnh
void inDuongDi(const int truoc[], int v) {
    vector<int> path;
    for (int i = v; i != -1; i = truoc[i]) {
        path.push_back(i);
    }
    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size(); i++) {
        cout << dinhKyHieu[path[i]];
        if (i < path.size() - 1) {
            cout << " -> ";
        }
    }
}

// Hàm in đường đi ngắn nhất và khoảng cách
void inKetQua(const int khoangCach[], const int truoc[], int src) {
    cout << "Dinh \t Khoang cach \t Duong di\n";
    for (int i = 0; i < V; i++) {
        cout << dinhKyHieu[src] << " -> " << dinhKyHieu[i] << "\t" << khoangCach[i] << "\t\t";
        if (khoangCach[i] != INF) {
            inDuongDi(truoc, i);
        }
        cout << "\n";
    }
}

// Hàm khởi tạo khoảng cách và đỉnh trước đó
void khoiTao(int khoangCach[], int truoc[], int src) {
    fill(khoangCach, khoangCach + V, INF);
    fill(truoc, truoc + V, -1);
    khoangCach[src] = 0;
}

// Hàm cập nhật khoảng cách và hàng đợi ưu tiên
void capNhatKhoangCach(int u, int v, int khoangCach[], int truoc[], priority_queue<iPair, vector<iPair>, greater<iPair>>& pq, int graph[V][V]) {
    khoangCach[v] = khoangCach[u] + graph[u][v];
    truoc[v] = u;
    pq.push({khoangCach[v], v});
}

// Hàm cập nhật hàng đợi ưu tiên
void capNhatHangDoi(priority_queue<iPair, vector<iPair>, greater<iPair>>& pq, int u, int v, int khoangCach[], int truoc[], int graph[V][V]) {
    if (graph[u][v] && khoangCach[u] + graph[u][v] < khoangCach[v]) {
        capNhatKhoangCach(u, v, khoangCach, truoc, pq, graph);
    }
}

// Hàm Dijkstra sử dụng priority_queue và pair
void dijkstra(int graph[V][V], int src) {
    int khoangCach[V]; // Mảng lưu khoảng cách ngắn nhất từ nguồn đến các đỉnh
    int truoc[V]; // Mảng lưu đỉnh trước đó trên đường đi ngắn nhất
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq; // Priority queue lưu cặp (khoảng cách, đỉnh)

    khoiTao(khoangCach, truoc, src); // Khởi tạo khoảng cách và đỉnh trước đó
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (int v = 0; v < V; v++) {
            capNhatHangDoi(pq, u, v, khoangCach, truoc, graph);
        }
    }

    inKetQua(khoangCach, truoc, src); // In kết quả
}

int main() {
    int graph[V][V] = {
        // A  B  C  D  E
        {0, 7, 0, 0, 1},  // A
        {7, 0, 3, 0, 8},  // B
        {0, 3, 0, 6, 2},  // C
        {0, 0, 6, 0, 7},  // D
        {1, 8, 2, 7, 0},  // E
    };

    int nguon = 0; // Đỉnh nguồn

    dijkstra(graph, nguon); // Chạy thuật toán Dijkstra

    return 0;
}