Chương trình C++ cho thuật toán Dijkstra tìm đường đi ngắn nhất

Thuật toán Dijkstra (hay Dijkstra's Shortest Path First - SPF) là thuật toán tìm đường đi ngắn nhất giữa các nút trong đồ thị, ví dụ như mạng lưới đường bộ. Thuật toán tạo cây đường đi ngắn nhất từ đỉnh nguồn (source) đến tất cả các đỉnh khác.

Dijkstra xây dựng tập hợp các nút có khoảng cách tối thiểu từ nguồn.

Các thành phần của đồ thị

• Đỉnh (vertices/nodes): ký hiệu v hoặc u.
• Cạnh có trọng số (weighted edges): (u,v) là cạnh, w(u,v) là trọng số.

Các bước thuật toán

1. Khởi tạo khoảng cách tất cả đỉnh = vô cực (INF), trừ đỉnh nguồn = 0.
2. Đưa đỉnh nguồn vào hàng đợi ưu tiên (min-priority queue) dạng (khoảng_cách, đỉnh).
3. Lấy đỉnh có khoảng cách nhỏ nhất từ hàng đợi (lúc đầu là nguồn).
4. Cập nhật khoảng cách các đỉnh kề: nếu "khoảng_cách_đỉnh_hiện_tại + trọng_số_cạnh < khoảng_cách_đỉnh_kế", cập nhật và đẩy vào hàng đợi.
5. Nếu đỉnh đã được thăm, bỏ qua.
6. Lặp lại cho đến khi hàng đợi rỗng.

Ví dụ đầu vào/đầu ra

Đồ thị 5 đỉnh (ma trận kề):
G[5][5] = {{0,1,0,3,10},
           {1,0,5,0,0},
           {0,5,0,2,1},
           {3,0,2,0,6},
           {10,0,1,6,0}}
n=5, u=0 (đỉnh nguồn)

Kết quả:
Distance of node1=1 Path=1<-0
Distance of node2=5 Path=2<-3<-0
Distance of node3=3 Path=3<-0
Distance of node4=6 Path=4<-2<-3<-0

Code ví dụ

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

#define MAX 5
#define INF 9999

void dijkstra(int G[MAX][MAX], int n, int startnode);

int main() {
    int G[MAX][MAX] = {{0,1,0,3,10},
                       {1,0,5,0,0},
                       {0,5,0,2,1},
                       {3,0,2,0,6},
                       {10,0,1,6,0}};
    int n = 5;
    int u = 0;
    dijkstra(G, n, u);
    return 0;
}

void dijkstra(int G[MAX][MAX], int n, int startnode) {
    int cost[MAX][MAX], distance[MAX], pred[MAX];
    int visited[MAX], count, mindistance, nextnode, i, j;
    
    // Tạo ma trận chi phí
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            cost[i][j] = (G[i][j] == 0) ? INF : G[i][j];
    
    // Khởi tạo
    for(i = 0; i < n; i++) {
        distance[i] = cost[startnode][i];
        pred[i] = startnode;
        visited[i] = 0;
    }
    distance[startnode] = 0;
    visited[startnode] = 1;
    count = 1;
    
    while(count < n - 1) {
        mindistance = INF;
        // Tìm đỉnh chưa thăm có khoảng cách nhỏ nhất
        for(i = 0; i < n; i++)
            if(distance[i] < mindistance && !visited[i]) {
                mindistance = distance[i];
                nextnode = i;
            }
        
        visited[nextnode] = 1;
        
        // Cập nhật khoảng cách các đỉnh kề
        for(i = 0; i < n; i++)
            if(!visited[i])
                if(mindistance + cost[nextnode][i] < distance[i]) {
                    distance[i] = mindistance + cost[nextnode][i];
                    pred[i] = nextnode;
                }
        count++;
    }
    
    // In kết quả
    for(i = 0; i < n; i++)
        if(i != startnode) {
            cout << "\nDistance of node " << i << " = " << distance[i];
            cout << "\nPath = " << i;
            j = i;
            do {
                j = pred[j];
                cout << "<-" << j;
            } while(j != startnode);
        }
}

Độ phức tạp

• Dùng mảng: O(V²)
• Dùng Min-Heap (Priority Queue): O((V+E) log V)
• Dùng Fibonacci Heap: O(E + V log V)

Lưu ý: Dijkstra chỉ hoạt động đúng với đồ thị không có cạnh âm.