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

Cho một đồ thị có đỉnh nguồn, bài toán yêu cầu tìm đường đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị.

Thuật toán Dijkstra là thuật toán tham lam để tìm đường đi ngắn nhất từ đỉnh nguồn đến các đỉnh còn lại.

Thuật toán

Bước 1: Tạo tập shortPath chứa các đỉnh thuộc cây đường đi ngắn nhất.
Bước 2: Khởi tạo tất cả khoảng cách là VÔ CỰC, gán khoảng cách đỉnh nguồn = 0 để được chọn đầu tiên.
Bước 3: Lặp cho đến khi mọi đỉnh đều trong shortPath.
    Bước 3.1: Chọn đỉnh chưa thăm có khoảng cách nhỏ nhất.
    Bước 3.2: Thêm đỉnh này vào shortPath.
    Bước 3.3: Cập nhật khoảng cách cho tất cả đỉnh kề. Nếu khoảng cách qua đỉnh hiện tại nhỏ hơn, cập nhật lại.

Mã nguồn C

#include <limits.h>
#include <stdio.h>
#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

int printSolution(int dist[], int n) {
    printf("Đỉnh \t Khoảng cách từ nguồn\n");
    for (int i = 0; i < V; i++)
        printf("%d \t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; 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];
    }
    printSolution(dist, V);
}

int main() {
    int graph[V][V] = {
        { 0, 6, 0, 0, 0, 0, 0, 8, 0 },
        { 6, 0, 8, 0, 0, 0, 0, 13, 0 },
        { 0, 8, 0, 7, 0, 6, 0, 0, 2 },
        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
        { 0, 0, 6, 14, 10, 0, 2, 0, 0 },
        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
        { 8, 13, 0, 0, 0, 0, 1, 0, 7 },
        { 0, 0, 2, 0, 0, 0, 6, 7, 0 }
    };
    dijkstra(graph, 0);
    return 0;
}

Kết quả

Đỉnh Khoảng cách từ nguồn
0 0
1 6
2 14
3 21
4 21
5 11
6 9
7 8
8 15