Chương trình C++ cài đặt thuật toán Dijkstra dùng Set

Cài đặt thuật toán Dijkstra tìm đường đi ngắn nhất từ một nguồn, sử dụng hai tập hợp (set): tập đỉnh đã đưa vào cây đường đi ngắn nhất và tập chưa đưa vào. Mỗi bước chọn đỉnh chưa trong tập có khoảng cách nhỏ nhất.

Thuật toán

Bắt đầu
  hàm dijkstra():
    1) Tạo set Set rỗng theo dõi đỉnh trong cây đường đi ngắn nhất.
    2) Gán khoảng cách INF cho tất cả đỉnh, nguồn = 0.
    3) Khi Set chưa chứa tất cả đỉnh:
       a) Chọn đỉnh u không trong Set có khoảng cách nhỏ nhất.
       b) Thêm u vào Set.
       c) Cập nhật khoảng cách các đỉnh kề v: nếu dist[u] + weight(u,v) < dist[v] thì cập nhật.
Kết thúc

Ví dụ

#include <iostream>
#include <climits>
#include <set>
using namespace std;
#define N 5

int minDist(int dist[], bool Set[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < N; v++)
        if (!Set[v] && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printSol(int dist[], int n) {
    cout << "Vertex Distance from Source\n";
    for (int i = 0; i < N; i++)
        cout << " \t\t \n" << i << " \t\t " << dist[i];
}

void dijkstra(int g[N][N], int src) {
    int dist[N];
    bool Set[N];
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX, Set[i] = false;
    dist[src] = 0;
    for (int c = 0; c < N - 1; c++) {
        int u = minDist(dist, Set);
        Set[u] = true;
        for (int v = 0; v < N; v++)
            if (!Set[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
    printSol(dist, N);
}

int main() {
    int g[N][N] = {{0, 4, 0, 0, 0},
                   {4, 0, 7, 0, 0},
                   {0, 8, 0, 9, 0},
                   {0, 0, 7, 0, 6},
                   {0, 2, 0, 9, 0}};
    dijkstra(g, 0);
    return 0;
}

Kết quả

Vertex Distance from Source
0       0
1       4
2       11
3       20
4       26