Chuyên đề đồ thị có trọng số

🛣️ Đường đi ngắn nhất: Dijkstra & Bellman-Ford

Bài học giúp học sinh hiểu cách tìm đường đi ngắn nhất từ một đỉnh nguồn đến các đỉnh còn lại. Trọng tâm là phân biệt Dijkstra cho trọng số không âm và Bellman-Ford khi có cạnh âm hoặc cần phát hiện chu trình âm.

DijkstraChọn đỉnh có dist nhỏ nhất
Bellman-FordRelax tất cả cạnh n−1 lần
Trực quanĐồ thị, heap, bảng dist
Ứng dụngĐường đi, chi phí, mạng lưới
Mục tiêuLý thuyếtDijkstraBellman-FordCode mẫuGiải thích codeThực hànhLỗi hay nhầmQuiz

Mục tiêu bài học

Học xong cần làm được

  • Hiểu bài toán đường đi ngắn nhất từ một nguồn.
  • Biết dùng Dijkstra cho đồ thị có trọng số không âm.
  • Biết dùng Bellman-Ford khi có cạnh âm.
  • Biết phát hiện chu trình âm bằng Bellman-Ford.
  • Biết lưu parent[] để truy vết đường đi.

Ví dụ đời sống

  • Tìm tuyến đường rẻ nhất giữa các thành phố.
  • Tìm thời gian truyền tin nhỏ nhất trong mạng.
  • Tối ưu chi phí chuyển hàng qua nhiều trạm.
  • Phát hiện mô hình chi phí bất thường có vòng âm.

1. Lý thuyết cốt lõi

Thuật toánÝ tưởngDùng khi nào?Độ phức tạp thường gặpĐiểm cần nhớ
DijkstraLuôn lấy đỉnh chưa xử lý có khoảng cách nhỏ nhất, rồi relax các cạnh đi ra.Trọng số cạnh không âm.O((n+m)log n) với heap.Nếu có cạnh âm, Dijkstra có thể sai.
Bellman-FordLặp qua tất cả cạnh n-1 lần để relax.Có thể có cạnh âm, cần phát hiện chu trình âm.O(nm)Chạy chậm hơn Dijkstra nhưng tổng quát hơn.
Relax cạnh là gì? Với cạnh u → v trọng số w, nếu dist[u] + w < dist[v] thì cập nhật dist[v] = dist[u] + w.
Chu trình âm: nếu sau n-1 vòng Bellman-Ford vẫn còn cập nhật được khoảng cách, tồn tại chu trình âm có thể đi tới từ nguồn. Khi đó không có đường đi ngắn nhất hữu hạn.

2. Mô phỏng Dijkstra

Đồ thị mẫu có trọng số dương. Dijkstra bắt đầu từ đỉnh 1, dùng heap để chọn đỉnh có dist nhỏ nhất.

Nhấn “Bước tiếp” để chạy Dijkstra.

3. Mô phỏng Bellman-Ford

Bellman-Ford xét toàn bộ cạnh nhiều vòng. Mô phỏng dưới đây có một cạnh âm nhưng không có chu trình âm.

Nhấn “Bước tiếp” để chạy Bellman-Ford.

4. Code mẫu

4.1. Dijkstra – C++

#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    vector<long long> dist(n + 1, INF);
    vector<int> parent(n + 1, -1);

    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<pair<long long,int>>
    > pq;

    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d != dist[u]) continue; // bỏ trạng thái cũ trong heap

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) cout << "INF ";
        else cout << dist[i] << ' ';
    }
    return 0;
}
import heapq

INF = 10**18
n, m, s = map(int, input().split())

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))

dist = [INF] * (n + 1)
parent = [-1] * (n + 1)

dist[s] = 0
pq = [(0, s)]

while pq:
    d, u = heapq.heappop(pq)

    if d != dist[u]:
        continue

    for v, w in adj[u]:
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            parent[v] = u
            heapq.heappush(pq, (dist[v], v))

print(*["INF" if x == INF else x for x in dist[1:]])

4.2. Bellman-Ford – phát hiện chu trình âm

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long w;
};

const long long INF = 4e18;

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;

    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    for (int i = 1; i <= n - 1; i++) {
        bool changed = false;

        for (auto e : edges) {
            if (dist[e.u] == INF) continue;

            if (dist[e.v] > dist[e.u] + e.w) {
                dist[e.v] = dist[e.u] + e.w;
                changed = true;
            }
        }

        if (!changed) break;
    }

    bool negativeCycle = false;
    for (auto e : edges) {
        if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.w) {
            negativeCycle = true;
        }
    }

    if (negativeCycle) {
        cout << "Co chu trinh am";
    } else {
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) cout << "INF ";
            else cout << dist[i] << ' ';
        }
    }
    return 0;
}
INF = 10**18
n, m, s = map(int, input().split())

edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

dist = [INF] * (n + 1)
dist[s] = 0

for _ in range(n - 1):
    changed = False

    for u, v, w in edges:
        if dist[u] == INF:
            continue

        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            changed = True

    if not changed:
        break

negative_cycle = False
for u, v, w in edges:
    if dist[u] != INF and dist[v] > dist[u] + w:
        negative_cycle = True

if negative_cycle:
    print("Co chu trinh am")
else:
    print(*["INF" if x == INF else x for x in dist[1:]])

5. Giải thích chi tiết code Dijkstra

Dijkstra dùng priority_queue để luôn lấy ra trạng thái có khoảng cách nhỏ nhất. Điểm dễ nhầm nhất là trong heap có thể tồn tại nhiều bản ghi của cùng một đỉnh. Vì vậy dòng if (d != dist[u]) continue; là cực kỳ quan trọng.

5.1. Các biến chính

  • adj[u]: danh sách các cạnh đi ra từ đỉnh u.
  • dist[v]: khoảng cách tốt nhất hiện biết từ nguồn đến v.
  • parent[v]: đỉnh đứng trước v trên đường đi ngắn nhất hiện tại.
  • pq: heap nhỏ, lưu các cặp {khoảng_cách, đỉnh}.

5.2. Luồng chạy chuẩn

  1. Khởi tạo dist[s] = 0, các đỉnh khác là vô cực.
  2. Đưa {0, s} vào heap.
  3. Lặp: lấy trạng thái có khoảng cách nhỏ nhất ra.
  4. Nếu trạng thái đó đã cũ thì bỏ qua.
  5. Relax tất cả cạnh đi ra từ đỉnh đang xét.

5.3. Vì sao heap có “trạng thái cũ”?

Trong C++ priority_queue không có thao tác giảm khóa trực tiếp như “decrease-key”. Khi tìm được khoảng cách tốt hơn cho một đỉnh, ta thường đẩy thêm bản ghi mới vào heap, chứ không xóa được bản ghi cũ ngay lập tức.
BướcThao tácHeap / dist thay đổiÝ nghĩa
1 Từ đỉnh 1 relax cạnh 1→2 trọng số 4 Đưa (4,2) vào heap, dist[2] = 4 Tạm thời biết đường tốt nhất đến 2 là 4.
2 Từ đỉnh 1 relax cạnh 1→3 trọng số 2 Đưa (2,3) vào heap, dist[3] = 2 Bước tiếp theo phải lấy đỉnh 3 vì 2 nhỏ hơn 4.
3 Từ đỉnh 3 relax cạnh 3→2 trọng số 1 Cập nhật dist[2] = 3, đưa thêm (3,2) vào heap Đỉnh 2 có đường mới tốt hơn: 1→3→2.
4 Heap vẫn còn bản ghi cũ (4,2) Nhưng dist[2] hiện tại đã là 3 (4,2) là trạng thái cũ, không còn đúng nữa.

5.4. Dòng quan trọng: bỏ trạng thái cũ trong heap

auto [d, u] = pq.top();
pq.pop();

if (d != dist[u]) continue; // bỏ trạng thái cũ trong heap
// Ví dụ heap có cả:
// (3, 2)  ← trạng thái mới, đúng
// (4, 2)  ← trạng thái cũ

// Khi pop ra (4, 2):
d = 4
u = 2

// Nhưng khoảng cách tốt nhất hiện tại là:
dist[2] = 3

// Vì 4 != 3 nên bỏ qua.
// Không cần relax cạnh đi ra từ đỉnh 2 bằng trạng thái cũ.
Không có dòng này thì sao? Chương trình có thể vẫn ra đúng trong một số phiên bản nếu phần relax luôn dùng dist[u], nhưng sẽ xử lý thừa rất nhiều trạng thái cũ, dễ bị chậm hoặc TLE. Nếu học sinh viết relax theo kiểu dùng trực tiếp d + w, việc xử lý trạng thái cũ còn dễ gây sai logic mô phỏng và truy vết đường đi.

5.5. Giải thích từng khối trong code C++

Đoạn codeÝ nghĩaLưu ý
const long long INF = 4e18;Đặt giá trị rất lớn để biểu diễn “chưa đi tới được”.Dùng long long vì tổng trọng số có thể lớn.
vector<vector<pair<int,int>>> adjLưu đồ thị dạng danh sách kề: từ u đi tới v với trọng số w.Nếu đồ thị vô hướng, phải thêm cả hai chiều.
priority_queue<..., greater<...>> pq;Tạo heap nhỏ để lấy trạng thái có khoảng cách nhỏ nhất.Mặc định C++ là heap lớn, nên cần greater.
if (d != dist[u]) continue;Bỏ bản ghi cũ trong heap.Đây là dòng học sinh rất hay quên.
if (dist[v] > dist[u] + w)Relax cạnh u→v.Nếu tìm được đường tốt hơn thì cập nhật.
parent[v] = u;Lưu lại đường đi: trước khi đến v là u.Dùng để in đường đi cụ thể từ nguồn đến đích.
Kết luận: Dòng if (d != dist[u]) continue; không phải là “trang trí”. Nó là cơ chế lọc rác trong heap, giúp Dijkstra chỉ xử lý trạng thái mới nhất và tốt nhất của mỗi đỉnh.

6. Thực hành nhanh với Dijkstra

Kết quả sẽ hiện ở đây.

7. Lỗi học sinh hay nhầm

Dùng Dijkstra khi có cạnh âm.
Dijkstra chỉ đảm bảo đúng khi trọng số không âm.
Không bỏ trạng thái cũ trong heap.
Dòng if (d != dist[u]) continue; giúp bỏ bản ghi cũ khi đỉnh đã có khoảng cách tốt hơn.
Dùng int cho khoảng cách lớn.
Nên dùng long long và INF đủ lớn.
Quên kiểm tra dist[u] == INF trong Bellman-Ford.
Nếu u chưa tới được thì không nên relax cạnh đi ra từ u.
Nhầm đồ thị có hướng và vô hướng.
Nếu vô hướng, phải thêm cả u → v và v → u.

8. Bài tập luyện tập phân loại

📘 Cơ bản

  1. Tính đường đi ngắn nhất từ 1 đến mọi đỉnh bằng Dijkstra.
  2. In khoảng cách từ s đến t.
  3. Đồ thị vô hướng: thêm cạnh hai chiều rồi chạy Dijkstra.

📗 Trung bình

  1. In đường đi cụ thể từ 1 đến n bằng mảng parent.
  2. Bellman-Ford phát hiện chu trình âm.
  3. So sánh kết quả Dijkstra và Bellman-Ford trên đồ thị không có cạnh âm.

📙 Nâng cao

  1. Đếm số đường đi ngắn nhất modulo M.
  2. Dijkstra nhiều nguồn.
  3. Đường đi ngắn nhất với ràng buộc số cạnh không quá k.

🐉 HSG định hướng

  1. 0-1 BFS khi trọng số chỉ là 0 hoặc 1.
  2. Floyd-Warshall cho mọi cặp đỉnh khi n nhỏ.
  3. Johnson’s algorithm khi cần all-pairs với cạnh âm nhưng không có chu trình âm.

9. Quiz kiểm tra nhanh

Câu 1. Dijkstra dùng được khi nào?
Câu 2. Bellman-Ford lặp relax tất cả cạnh tối đa bao nhiêu lần trước khi kiểm tra chu trình âm?
Câu 3. Vì sao cần if (d != dist[u]) continue; trong Dijkstra dùng heap?

Tổng kết

Dijkstra nhanh và dùng nhiều nhất khi trọng số không âm. Bellman-Ford chậm hơn nhưng xử lý được cạnh âm và phát hiện chu trình âm. Khi làm bài thi, hãy đọc kỹ ràng buộc trọng số trước khi chọn thuật toán.
⬅️ Quay lại chương 10