Nhiều lập trình viên gặp khó khăn với các thuật toán tìm đường đi ngắn nhất. Bài viết này sẽ phân tích chi tiết hai thuật toán phổ biến: SPFA và Dijkstra.

Thuật toán SPFA (Shortest Path Faster Algorithm)

Nguyên lý hoạt động

• Khởi tạo khoảng cách tại đỉnh nguồn bằng 0, các đỉnh khác bằng vô cùng
• Đưa đỉnh nguồn vào hàng đợi và đánh dấu đang xử lý (vis = true)
• Lặp: lấy đỉnh đầu hàng đợi, bỏ đánh dấu, thử nới lỏng các cạnh kề
• Nếu nới lỏng thành công: kiểm tra chu trình âm thông qua số lần vào hàng đợi (cnt)
• Nếu không có chu trình âm: đánh dấu và đưa đỉnh đó vào hàng đợi
• Dừng khi phát hiện chu trình âm hoặc hàng đợi rỗng

Mã nguồn tham khảo

Phiên bản 1: Có cạnh trùng (cnt đếm số lần vào hàng đợi)

struct Edge {
    int to, weight;
};

int dist[MAXN];
bool inQueue[MAXN];
int queuedCount[MAXN];

bool spfa(vector<Edge> graph[], int source, int n) {
    queue<int> q;
    memset(dist, 0x3f, (n + 1) * sizeof(int));
    memset(queuedCount, 0, (n + 1) * sizeof(int));
    memset(inQueue, 0, (n + 1) * sizeof(bool));
    
    q.push(source);
    dist[source] = 0;
    inQueue[source] = true;
    queuedCount[source]++;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;
            
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                
                if (!inQueue[v]) {
                    queuedCount[v]++;
                    if (queuedCount[v] >= n) return false;
                    inQueue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return true;
}

Phiên bản 2: Không có cạnh trùng (cnt đếm số lần nới lỏng)

struct Edge {
    int to, weight;
};
vector<Edge> graph[MAXN];
int dist[MAXN], relaxCount[MAXN];
bool inQueue[MAXN];
int n;

queue<int> q;
bool spfa(int source) {
    memset(dist, 0x3f, (n + 1) * sizeof(int));
    q.push(source);
    inQueue[source] = true;
    dist[source] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        for (auto e : graph[u]) {
            int v = e.to, w = e.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                relaxCount[v] = relaxCount[u] + 1;
                if (relaxCount[v] >= n) return false;
                if (!inQueue[v]) {
                    inQueue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return true;
}

Lưu ý quan trọng

• Ý nghĩa của biến đếm (cnt/relaxCount) phụ thuộc vào việc có cạnh trùng hay không
• Không quên memset các mảng trước khi sử dụng
• Đánh dấu vis khi: đưa vào hàng đợi lần đầu, lấy ra khỏi hàng đợi, và đưa vào lại hàng đợi
• Kiểm tra kiểu dữ liệu của trọng số cạnh (int, long long,...)

Thuật toán Dijkstra

Nguyên lý hoạt động

• Khởi tạo khoảng cách tại đỉnh nguồn bằng 0
• Đưa đỉnh nguồn vào hàng đợi ưu tiên (min-heap)
• Lặp: lấy đỉnh có dist nhỏ nhất từ hàng đợi
• Nếu đỉnh đã được xác nhận đường đi ngắn nhất (vis = true) thì bỏ qua
• Nếu chưa: đánh dấu đã xác nhận, nới lỏng các cạnh kề
• Với mỗi cạnh nới lỏng thành công, đưa đỉnh đích vào hàng đợi

Mã nguồn tham khảo

struct Edge {
    int to, weight;
};

struct Node {
    int distance, vertex;
    bool operator>(const Node& other) const {
        return distance > other.distance;
    }
};

vector<Edge> adjacency[MAXN];
int dist[MAXN], visited[MAXN];
priority_queue<Node, vector<Node>, greater<Node>> pq;

void dijkstra(int n, int source) {
    memset(dist, 0x3f, (n + 1) * sizeof(int));
    memset(visited, 0, (n + 1) * sizeof(int));
    dist[source] = 0;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int u = pq.top().vertex;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        
        for (auto edge : adjacency[u]) {
            int v = edge.to, w = edge.weight;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

Lưu ý quan trọng

• Cần hai cấu trúc dữ liệu: Edge cho danh sách kề, Node cho hàng đợi ưu tiên
• Không đánh dấu visited cho đỉnh nguồn hoặc bất kỳ đỉnh nào trước khi xử lý
• Phải lưu cấu trúc Node trong hàng đợi ưu tiên, không chỉ lưu đỉnh
• Kiểm tra visited sau khi lấy đỉnh từ hàng đợi, trước khi xử lý