Bài BFS cho đường đi ngắn nhất khi mọi cạnh nặng như nhau — mỗi bước đúng một đơn vị. Nhưng bản đồ thật không như thế: đoạn đường này 2 km, đoạn kia 10 km, chuyến bay này rẻ, chuyến kia đắt. Khi cạnh có trọng số, ta cần Dijkstra. Bài này đo hai điều về Dijkstra mà lý thuyết hay nói lướt qua: nó là một thuật toán tham lam — mà bài 19 đã dạy phải nghi ngờ — vậy tại sao nó đúng, và đúng tới khi nào? Và cấu trúc dữ liệu bên trong nó quan trọng tới mức nào?
Một thuật toán tham lam, nhưng lần này đúng
Dijkstra giữ một khoảng cách tạm thời tới mỗi đỉnh (khởi đầu là vô cực, trừ đỉnh nguồn bằng 0). Mỗi bước nó làm một lựa chọn tham lam: chốt (finalize) đỉnh có khoảng cách tạm nhỏ nhất trong số các đỉnh chưa chốt, coi khoảng cách đó là cuối cùng, rồi "nới lỏng" (relax) các cạnh đi ra — nếu đi qua đỉnh vừa chốt tới một hàng xóm rẻ hơn khoảng cách tạm hiện tại của hàng xóm đó, cập nhật. Lặp tới khi chốt hết.
Nhưng khoan — bài 19 vừa cho thấy tham lam có thể sai (đổi tiền với hệ xu lạ). Vậy sao Dijkstra lại đúng? Câu trả lời nằm ở một điều kiện: mọi trọng số phải không âm. Khi mọi cạnh ≥ 0, đi thêm một cạnh chỉ có thể làm đường dài ra, không bao giờ ngắn lại. Nhờ vậy, khi Dijkstra chốt đỉnh gần nhất, không có đường nào khác (qua các đỉnh xa hơn còn chưa chốt) có thể quay lại làm nó ngắn hơn — nên "chốt" là chắc chắn đúng. Đây là greedy có bằng chứng, khác greedy đổi tiền chỉ "trông hợp lý". Tôi đo cả hai mặt: điều kiện đó thật sự cần tới đâu, và cấu trúc dữ liệu ảnh hưởng ra sao.
Đo: cấu trúc dữ liệu quyết định Dijkstra có dùng được không
Câu "lấy đỉnh gần nhất chưa chốt" nghe đơn giản, nhưng cách làm nó quyết định tốc độ. Hai cách: quét tuyến tính cả mảng khoảng cách để tìm nhỏ nhất (đơn giản, O(V²) tổng), hoặc dùng một hàng đợi ưu tiên — chính là heap ở bài 10 — để lấy nhỏ nhất trong O(log V), cho tổng O((V+E) log V). Tôi đo cả hai trên đồ thị 3000 đỉnh với mật độ cạnh tăng dần:
bậc trung bình E heap mảng heap/mảng
4 12 000 0,16 ms 5,79 ms 0,03 (heap nhanh 36 lần)
30 90 000 0,53 ms 6,11 ms 0,09
300 900 000 2,94 ms 7,61 ms 0,39
1500 4 500 000 11,44 ms 12,68 ms 0,90 (gần ngang)
Trên đồ thị thưa (ít cạnh — bậc 4, như bản đồ đường bộ hay mạng xã hội), heap nhanh hơn mảng 36 lần. Càng dày cạnh, khoảng cách càng thu hẹp, tới đồ thị gần đầy đủ thì hai cách gần ngang nhau (mảng thậm chí bắt đầu nhỉnh hơn nhờ hằng số nhỏ, không có phí duy trì heap). Bài học thực dụng: hầu hết đồ thị thật là thưa, và trên đó heap là thứ khiến Dijkstra chạy được ở quy mô lớn — mảng O(V²) sẽ chết trên một triệu đỉnh, còn heap O((V+E) log V) thì không. Cấu trúc dữ liệu không phải chi tiết trang trí; nó là ranh giới giữa "chạy được" và "không".
Một lần tôi đo hớ: greedy đúng, nhưng chỉ khi không có cạnh âm
Cú hớ của tôi là quên mất chữ "có điều kiện". Tôi nghĩ về Dijkstra như "thuật toán luôn cho đường ngắn nhất" — một sự thật tuyệt đối. Nhưng nó là greedy, và như bài 19 dạy, tính đúng của greedy luôn kèm một điều kiện. Với Dijkstra, điều kiện là trọng số không âm. Tôi dựng một đồ thị nhỏ có đúng một cạnh âm để xem nó gãy ra sao:
đồ thị: 0->1 (trọng số 4), 0->2 (5), 2->1 (-3)
đường ngắn nhất thật 0->1 = 0->2->1 = 5 + (-3) = 2
Dijkstra : dist[1] = 4 (SAI)
Bellman-Ford: dist[1] = 2 (đúng)
Dijkstra chốt đỉnh 1 ở khoảng cách 4 (vì lúc đó 4 là nhỏ nhất), khóa lại, rồi mới xét tới đỉnh 2 — nhưng cạnh 2->1 = -3 lẽ ra cho đường 0->2->1 = 2 ngắn hơn. Vì đỉnh 1 đã bị chốt, Dijkstra không bao giờ nhìn lại, và trả về 4 — sai. Cạnh âm phá đúng cái giả định làm nền cho tính đúng của Dijkstra: rằng đi thêm cạnh chỉ làm đường dài ra. Một cạnh âm khiến "đi thêm" có thể làm đường ngắn lại, nên một đỉnh đã chốt vẫn có thể cải thiện — nhưng Dijkstra không cho phép điều đó. Và nó sai lặng lẽ: không lỗi, không cảnh báo, chỉ một con số sai. Bài học đo lường: một thuật toán "luôn đúng" gần như luôn có nghĩa "luôn đúng trong điều kiện của nó", và biết điều kiện đó là biết khi nào nó sẽ phản bội bạn. Muốn chịu được cạnh âm phải đổi sang Bellman-Ford, chậm hơn nhưng không dựa vào giả định không âm.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên, một cây quyết định gọn: không trọng số thì BFS (đủ và nhanh hơn, khỏi heap); có trọng số không âm thì Dijkstra; có cạnh âm thì Bellman-Ford. Chọn nhầm rất dễ và thường sai lặng lẽ — dùng Dijkstra cho đồ thị có chi phí âm (ví dụ mô hình hóa "được thưởng điểm" bằng cạnh âm) sẽ cho đáp án trông hợp lý nhưng sai. Luôn hỏi: đồ thị của tôi có cạnh âm không?
Hệ quả thứ hai: cấu trúc dữ liệu bên trong một thuật toán không phải chi tiết, nó là yếu tố quyết định quy mô dùng được. Cùng một Dijkstra, đổi mảng thành heap biến nó từ O(V²) — vô dụng ở triệu đỉnh — thành O((V+E) log V) — chạy tốt. Đây là lý do các bài trước về heap, cây, bảng băm không phải kiến thức tách rời: chúng là những viên gạch quyết định các thuật toán lớn có khả thi hay không. Khi một thuật toán chậm, thủ phạm thường là cấu trúc dữ liệu chọn sai bên trong nó.
Hệ quả thứ ba là con số mang theo: Dijkstra là greedy ĐÚNG nhờ điều kiện trọng số không âm — vi phạm bằng một cạnh âm là nó trả sai lặng lẽ (dist 4 thay vì 2); và cấu trúc dữ liệu quyết định tốc độ: heap đưa nó về O((V+E) log V), nhanh hơn mảng O(V²) 36 lần trên đồ thị thưa (nơi hầu hết đồ thị thật nằm). Một thuật toán kinh điển vẫn có một điều kiện đúng và một lựa chọn cài đặt, và bỏ qua cái nào cũng dẫn tới hoặc kết quả sai hoặc hiệu năng chết.
Thử ba mươi giây
Nếu bạn dùng Dijkstra ở đâu đó, hỏi hai câu. Thứ nhất: đồ thị của tôi có cạnh trọng số âm không? Chi phí âm hay xuất hiện khi bạn mô hình hóa "phần thưởng", "giảm giá", "hoàn tiền" thành cạnh — nếu có, Dijkstra sẽ sai, bạn cần Bellman-Ford. Thứ hai: tôi đang lấy đỉnh gần nhất bằng cách nào — quét cả mảng, hay dùng hàng đợi ưu tiên? Nếu đồ thị lớn và thưa mà bạn đang quét mảng, bạn đang chạy một Dijkstra O(V²) mà đáng lẽ chỉ O((V+E) log V). Thử vẽ nhanh đồ thị 3 đỉnh có cạnh âm ở trên ra giấy và "chạy" Dijkstra bằng tay — bạn sẽ thấy chính mắt cái khoảnh khắc nó chốt sai một đỉnh và không bao giờ sửa. Đó là toàn bộ giới hạn của thuật toán, gói trong ba đỉnh.
