Dijkstra với heap cho đồ thị có trọng số

Giới thiệu

Bài này học Dijkstra tìm đường rẻ nhất có trọng số. Thuật toán này mở rộng BFS nhờ heap lấy đỉnh gần nhất.

Kiến thức cần nhớ

Vì sao BFS thua

• BFS đếm số cạnh nên chọn đường 1 chặng kẹt xe.
• Thực tế cần tổng thời gian nhỏ nhất, không phải ít chặng.
• Ví dụ đời thường: cao tốc 2 chặng 20 phút thắng tắt 1 chặng 60 phút.
• Cạnh có trọng số thì phải dùng Dijkstra.

Vòng lặp Dijkstra

• Giữ bảng khoảng cách tốt nhất, nguồn bằng 0, còn lại vô cùng.
• Lặp: lấy đỉnh chưa chốt gần nhất rồi chốt nó.
• Nới lỏng lân cận: qua đỉnh mới mà rẻ hơn thì cập nhật.
• Ví dụ đời thường: chốt quán gần nhất rồi dò đường từ đó đi tiếp.

Heap và cấm cạnh âm

• Quét tìm đỉnh gần nhất tốn $O(n)$, heap chỉ tốn $O(log n)$.
• Nới lỏng thành công thì cập nhật giảm vị trí trên heap.
• Cạnh âm phá bẫy chốt: đã chốt vẫn có thể rẻ hơn nữa.
• Ví dụ đời thường: nợ âm làm mọi tính toán tiền sai lệch.

# Ý tưởng nới lỏng trong Dijkstra
INF = float('inf')  # vô cùng ban đầu
dist = {s: 0}  # nguồn bằng 0
# lấy đỉnh gần nhất từ heap rồi xét
for v, w in ke[u]:  # từng lân cận của u
    if dist[u] + w < dist.get(v, INF):  # đi qua u rẻ hơn
        dist[v] = dist[u] + w  # cập nhật rẻ hơn

Ví dụ

• Input: 2 đỉnh 1 cạnh trọng số 7 -> Output: khoảng cách đích bằng 7.
• Câu này cho thấy chỉ cần một lần nới lỏng.
• Input: đồ thị có cạnh âm mà chạy Dijkstra -> Output: đáp án sai ở bước chốt đầu.
• Câu này cho thấy điều kiện không âm là bắt buộc.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-042/. Trọng số là long long không âm.

Bài 1: Dijkstra với heap

struct WEdge { int to; long long w; };
using WGraph = std::vector<std::vector<WEdge>>;
struct Result { std::vector<long long> dist; std::vector<int> parent; };
Result dijkstra(const WGraph &g, int s);                 // dùng std::priority_queue, lazy deletion
std::vector<int> path(const Result &r, int t);           // rỗng nếu không tới được

Ràng buộc

• Không tới được thì dist = LLONG_MAX (hoặc hằng INF).
• Bỏ qua mục cũ trong heap khi d > dist[u].
• Gặp cạnh âm thì ném std::invalid_argument.

Cạnh có hướng: 0->1 (4), 0->2 (1), 2->1 (2), 1->3 (1), 2->3 (5)
dist từ 0     -> [0, 3, 1, 4]
path(3)       -> [0, 2, 1, 3]

Bài 2: So với cách quét mảng

Viết dijkstraArray không dùng heap: mỗi lượt quét tìm đỉnh chưa chốt gần nhất, $O(V^2)$.

Đo 2 bản trên 2 loại đồ thị:

loại         V        E           heap(ms)   array(ms)
thưa         10^4     5*10^4      ...        ...
dày          2000     4*10^6/2    ...        ...

Kết luận: đồ thị nào hợp bản nào, giải thích bằng $O((V+E)\log V)$ và $O(V^2)$.

Bài 3: Bản đồ thật và cạnh âm (nâng cao)

1. Đọc file đường phố u v phút (tự tạo 30 nút hoặc tải dữ liệu DIMACS nhỏ). Trả lời 10 truy vấn s t: thời gian và đường đi.
2. Dừng sớm khi đích t được chốt. Đếm số đỉnh đã chốt, so với chạy hết.
3. Dựng đồ thị 4 đỉnh có 1 cạnh âm mà Dijkstra (bỏ kiểm tra cạnh âm) cho đáp án sai. Chạy Bellman-Ford để có đáp án đúng. Giải thích bước chốt nào bị sai.

✅ Tiêu chí hoàn thành

• Test mẫu pass. Kết quả khớp dijkstraArray trên 100 đồ thị ngẫu nhiên.
• Bảng Bài 2 có số thật và kết luận.
• Bài 3 có ví dụ cạnh âm cụ thể kèm giải thích.
• Giải thích được vì sao mỗi đỉnh chỉ cần chốt 1 lần khi trọng số không âm.

❓ Câu hỏi ôn tập

• Vì sao BFS chọn nhầm trên đồ thị trọng số?
• Vòng lặp Dijkstra gồm 2 việc gì?
• Heap giúp Dijkstra nhanh ở chỗ nào?
• Vì sao cấm cạnh âm với Dijkstra?

🌕 Bạn đã hoàn thành ngày 42. Làm hết bài tập phía trên rồi sang ngày tiếp theo.