Untitled

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int INF = INT_MAX; // Định nghĩa giá trị vô cùng

void dijkstra(int start, const vector<vector<int>>& graph, vector<int>& dist, vector<int>& prev) {
    int n = graph.size(); // Số lượng đỉnh trong đồ thị
    vector<bool> visited(n, false); // Danh sách đánh dấu các đỉnh đã xét

    dist[start] = 0; // Khoảng cách từ đỉnh xuất phát đến chính nó là 0

    for (int i = 0; i < n; ++i) {
        // Tìm đỉnh có khoảng cách nhỏ nhất chưa được xét
        int u = -1;
        int min_dist = INF;

        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }

        if (u == -1) break; // Không tìm thấy đỉnh mới, dừng thuật toán

        visited[u] = true; // Đánh dấu đỉnh u đã được xét

        // Cập nhật khoảng cách tới các đỉnh kề của u
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && !visited[v]) { // Có cạnh nối u đến v và v chưa được xét
                int new_dist = dist[u] + graph[u][v];
                if (new_dist < dist[v]) { // Nếu khoảng cách mới nhỏ hơn
                    dist[v] = new_dist; // Cập nhật khoảng cách
                    prev[v] = u; // Lưu đỉnh trước đó
                }
            }
        }
    }
}

int main() {
    int n = 5; // Số đỉnh
    vector<vector<int>> graph = {
        {0, 10, 3, 0, 0},
        {0, 0, 1, 2, 0},
        {0, 4, 0, 8, 2},
        {0, 0, 0, 0, 7},
        {0, 0, 0, 9, 0}
    };

    vector<int> dist(n, INF); // Mảng lưu khoảng cách ngắn nhất từ đỉnh xuất phát
    vector<int> prev(n, -1); // Mảng lưu đỉnh liền kề trước đó trong đường đi ngắn nhất

    int start = 0; // Đỉnh bắt đầu
    dijkstra(start, graph, dist, prev);

    for (int i = 0; i < n; ++i) {
        cout << "Khoảng cách từ " << start << " đến " << i << " là " << dist[i] << endl;
    }

    return 0;
}