Cấu trúc dữ liệu và Giải thuật Bài 48: Tìm đường đi ngắn nhất trên đồ thị có trọng số với Thuật toán Dijkstra.
Breadth-First Search (BFS) hoạt động hoàn hảo khi mọi bước đi đều có cái giá bằng nhau. Tuy nhiên, trên mạng lưới thực tế, không có sự bình đẳng đó.
Hãy lấy ví dụ về việc điều phối tàu Metro Line 1. Đoạn đường từ Bến Thành đến Ba Son có thể mất 3 phút, nhưng từ Ba Son đến Văn Thánh lại mất 6 phút. Hoặc trong mạng lưới Microservices, gọi từ Service A sang Service B mất 10ms, nhưng từ B sang C qua một Data Center khác mất tận 50ms. Trọng số (thời gian, độ trễ, chi phí xăng xe) đã thay đổi hoàn toàn luật chơi. Việc đi qua ít trạm nhất (BFS) không còn đồng nghĩa với việc đến đích nhanh nhất.
Để giải quyết bài toán Đồ thị có trọng số (Weighted Graph), năm 1956, nhà khoa học máy tính Edsger W. Dijkstra đã thiết kế ra một thuật toán định hình lại toàn bộ ngành bản đồ số và viễn thông.
1. Nguyên lý Lòng tham (Greedy Approach) và Sự kết hợp hoàn hảo
Tư duy cốt lõi của thuật toán Dijkstra cực kỳ thực dụng: Tại mỗi bước đi, hãy luôn chọn con đường có tổng chi phí (khoảng cách) ngắn nhất hiện tại để khám phá tiếp.
Để thực thi triết lý "lòng tham" này, chúng ta không thể dùng Hàng đợi (Queue) bình thường của BFS (FIFO), vì người đến trước chưa chắc đã là người có chi phí rẻ nhất. Đây là lúc Hàng đợi ưu tiên (Priority Queue / Min-Heap) từ Bài 38 tỏa sáng rực rỡ.
Thuật toán cần 3 cấu trúc dữ liệu phối hợp đồng thời:
-
Danh sách kề có trọng số: Nơi lưu trữ mạng lưới (ví dụ:
A -> Bmất 5). -
Bảng lưu Khoảng cách (Distance Map): Ghi nhớ chi phí rẻ nhất để đi từ Đỉnh xuất phát đến tất cả các đỉnh khác. Ban đầu, đỉnh xuất phát có chi phí là
0, toàn bộ các đỉnh còn lại được khởi tạo là Vô cực ($\infty$). -
Min-Heap: Đóng vai trò là radar quét. Nó luôn bốc cái Đỉnh có khoảng cách ngắn nhất hiện tại ra khỏi hàng đợi để tiếp tục loang ra xung quanh.
2. Mô phỏng thuật toán
Giả sử bạn xuất phát từ Bến Thành.
-
Bước 1: Đẩy Bến Thành (chi phí 0) vào Min-Heap.
-
Bước 2: Rút Bến Thành ra khỏi Heap. Quét các ga lân cận (ví dụ: Ba Son mất 3, Nhà hát Thành phố mất 2). Cập nhật Bảng khoảng cách: Ba Son = 3, Nhà hát TP = 2. Đẩy cả hai vào Min-Heap.
-
Bước 3: Heap tự động đưa Nhà hát TP (có chi phí 2, nhỏ hơn 3) lên đỉnh. Rút Nhà hát TP ra. Từ đây, nếu phát hiện một đường vòng qua Ba Son chỉ mất thêm 0.5 phút (tổng chi phí từ Bến Thành = 2 + 0.5 = 2.5), hệ thống nhận thấy
2.5 < 3(kỷ lục cũ). Nó lập tức ghi đè kỷ lục mới vào Bảng khoảng cách và đẩy Ba Son (với trọng số 2.5) vào lại Min-Heap. -
Bước 4: Lặp lại cho đến khi Min-Heap rỗng. Bảng khoảng cách lúc này chứa chi phí tối ưu tuyệt đối từ Bến Thành đến mọi ga trên tuyến.
3. Triển khai lõi thuật toán bằng Golang
Để mã nguồn tinh gọn, đoạn code dưới đây tập trung vào luồng logic của Dijkstra, giả định chúng ta đã có sẵn một đối tượng MinHeap (được triển khai bằng container/heap như ở Bài 39).
Go
import "math"
// Cấu trúc một Cạnh (Edge)
type Edge struct {
To string
Weight int
}
// Cấu trúc Đồ thị có trọng số
type WeightedGraph struct {
AdjList map[string][]Edge
}
// Thuật toán Dijkstra
func (g *WeightedGraph) Dijkstra(start string) map[string]int {
// 1. Khởi tạo Bảng khoảng cách với giá trị Vô cực
distances := make(map[string]int)
for vertex := range g.AdjList {
distances[vertex] = math.MaxInt32
}
distances[start] = 0 // Điểm xuất phát có khoảng cách = 0
// 2. Khởi tạo Min-Heap và đẩy điểm xuất phát vào
pq := &MinHeap{}
heap.Init(pq)
heap.Push(pq, &Item{Node: start, Distance: 0})
// 3. Vòng lặp khám phá
for pq.Len() > 0 {
// Rút đỉnh có khoảng cách NGẮN NHẤT hiện tại ra khỏi Heap
currentItem := heap.Pop(pq).(*Item)
current := currentItem.Node
currentDist := currentItem.Distance
// Tối ưu hóa: Nếu phát hiện một đỉnh lấy ra từ Heap có chi phí lớn hơn
// kỷ lục đã ghi nhận (do bị trùng lặp cập nhật trong quá khứ), bỏ qua ngay.
if currentDist > distances[current] {
continue
}
// Quét các đỉnh kề (Hàng xóm)
for _, edge := range g.AdjList[current] {
neighbor := edge.To
weight := edge.Weight
// Tính toán tổng quãng đường nếu đi qua đỉnh hiện tại
newDist := currentDist + weight
// Nếu tìm thấy một con đường RẺ HƠN kỷ lục cũ
if newDist < distances[neighbor] {
// Cập nhật kỷ lục mới
distances[neighbor] = newDist
// Đẩy kỷ lục mới vào Min-Heap để hệ thống tiếp tục loang ra từ đây
heap.Push(pq, &Item{Node: neighbor, Distance: newDist})
}
}
}
// Trả về bảng chứa toàn bộ đường đi ngắn nhất
return distances
}
4. Phân tích Hiệu năng (Big-O)
Sức mạnh của thuật toán phụ thuộc hoàn toàn vào cấu trúc Min-Heap:
-
Mỗi Đỉnh () được lấy ra khỏi Heap 1 lần:
-
Mỗi Cạnh () được duyệt qua và có thể kích hoạt thao tác đẩy vào Heap:
-
Tổng thời gian: .
Đây là tốc độ cực kỳ ấn tượng. Google Maps có thể tính toán đường đi giữa hai thành phố xuyên qua hàng vạn ngã tư chỉ trong vài mili-giây chính là nhờ nền tảng này (dù họ đã nâng cấp nó bằng A* - một biến thể của Dijkstra kết hợp thuật toán Heuristic).
5. Ứng dụng ở tầng Mạng lõi (Network Routing)
Dijkstra không chỉ là phần mềm, nó là giao thức phần cứng kết nối Internet toàn cầu:
- Giao thức OSPF (Open Shortest Path First): Các Router lõi của các nhà mạng (VNPT, Viettel) liên tục trao đổi trạng thái liên kết cho nhau. Mỗi Router sẽ tự xây dựng một bản đồ Đồ thị trong RAM, sau đó chạy thuật toán Dijkstra để quyết định xem gói tin (Packet) tiếp theo nên được bắn qua cổng cáp quang nào để đến đích với độ trễ (Latency) thấp nhất.
Gót chân Achilles của Dijkstra:
Lòng tham của Dijkstra hoạt động dựa trên một niềm tin tuyệt đối: "Mọi bước đi tiến lên phía trước đều tốn kém thêm (Trọng số lớn hơn hoặc bằng 0)."
Nếu Đồ thị của bạn xuất hiện Trọng số âm (Negative Weights) — ví dụ: đi qua một con đường thay vì mất xăng, bạn lại được tặng thêm xăng — thuật toán Dijkstra sẽ lập tức sụp đổ và đưa ra kết quả sai lệch, vì nó không bao giờ có khái niệm "quay lại kiểm tra một con đường đã chốt vì biết đâu ở tương lai nó được trừ tiền".
Để đối phó với những hệ thống tài chính hoặc mạng lưới có chu trình âm (như giao dịch chênh lệch tỷ giá hối đoái - Arbitrage), chúng ta phải từ bỏ lòng tham để dùng một chiến thuật quét toàn diện và càn lướt hơn.
All rights reserved
