Hướng Dẫn Cài Đặt Thuật Toán Dijkstra Trong C

Thuật toán Dijkstra là một thuật toán phổ biến để tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm. Dưới đây là cách cài đặt thuật toán Dijkstra trong ngôn ngữ lập trình C.

#include <stdio.h>
#include <limits.h>

#define V 9 // Số lượng đỉnh trong đồ thị

// Hàm tìm đỉnh với khoảng cách ngắn nhất từ tập các đỉnh chưa được xử lý
int minDistance(int dist[], int sptSet[]) {
   int min = INT_MAX, min_index;
   
   for (int v = 0; v < V; v++)
     if (sptSet[v] == 0 && dist[v] <= min)
         min = dist[v], min_index = v;
   
   return min_index;
}

// Hàm in kết quả khoảng cách từ nguồn đến tất cả các đỉnh khác
void printSolution(int dist[]) {
   printf("Đỉnh \t Khoảng Cách từ Nguồn\n");
   for (int i = 0; i < V; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}

// Hàm thực hiện thuật toán Dijkstra cho một đồ thị được biểu diễn bằng ma trận kề
void dijkstra(int graph[V][V], int src) {
     int dist[V]; // dist[i] sẽ giữ khoảng cách ngắn nhất từ src đến i

     int sptSet[V]; // sptSet[i] sẽ đúng nếu đỉnh i được bao gồm trong cây đường đi ngắn nhất
                    // hoặc khoảng cách ngắn nhất từ src đến i được xác định

     // Khởi tạo tất cả các khoảng cách là INFINITE và sptSet[] là false
     for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = 0;

     // Khoảng cách của đỉnh nguồn từ chính nó luôn là 0
     dist[src] = 0;

     // Tìm đường đi ngắn nhất cho tất cả các đỉnh
     for (int count = 0; count < V-1; count++) {
       // Chọn đỉnh có khoảng cách tối thiểu từ tập hợp các đỉnh chưa xử lý
       // u luôn là src ở lần lặp đầu tiên
       int u = minDistance(dist, sptSet);

       // Đánh dấu đỉnh được chọn là đã xử lý
       sptSet[u] = 1;

       // Cập nhật giá trị khoảng cách của các đỉnh lân cận của đỉnh được chọn
       for (int v = 0; v < V; v++)

         // Cập nhật dist[v] chỉ khi không có trong sptSet, có một cạnh từ
         // u đến v, và tổng trọng số của đường đi từ src đến v qua u là
         // nhỏ hơn giá trị hiện tại của dist[v]
         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                       && dist[u] + graph[u][v] < dist[v])
            dist[v] = dist[u] + graph[u][v];
     }

     // in bảng khoảng cách
     printSolution(dist);
}

// Hàm chính để kiểm tra các hàm trên
int main() {
   // Ví dụ: Ma trận kề biểu diễn đồ thị
   int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                      {4, 0, 8, 0, 0, 0, 0, 11, 0},
                      {0, 8, 0, 7, 0, 4, 0, 0, 2},
                      {0, 0, 7, 0, 9, 14, 0, 0, 0},
                      {0, 0, 0, 9, 0, 10, 0, 0, 0},
                      {0, 0, 4, 14, 10, 0, 2, 0, 0},
                      {0, 0, 0, 0, 0, 2, 0, 1, 6},
                      {8, 11, 0, 0, 0, 0, 1, 0, 7},
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}
                     };

   dijkstra(graph, 0); // Gọi hàm dijkstra với đỉnh nguồn là 0

   return 0;
}

Đây là một cách tiếp cận cơ bản và trực quan để cài đặt thuật toán Dijkstra trong C. Cài đặt này sử dụng ma trận kề để biểu diễn đồ thị, với V là số lượng đỉnh. Để cải thiện hiệu suất, có thể sử dụng cấu trúc dữ liệu ưu tiên hàng đợi (priority queue) thay cho việc tìm kiếm tuyến tính trong hàm minDistance.

Hãy nhớ rằng thuật toán này chỉ hoạt động chính xác khi tất cả các trọng số của cạnh đều không âm. Đối với các trường hợp có cạnh âm, bạn cần sử dụng thuật toán khác như Bellman-Ford.