THUẬT TOÁN DIJKSTRA – TÌM ĐƯỜNG ĐI NGẮN NHẤT
Dijkstra là thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong đồ thị có trọng số không âm.
📌 Ý tưởng chính
-
Giống như bạn đứng ở đỉnh xuất phát, từ từ mở rộng sang các đỉnh gần nhất, luôn chọn đường ngắn nhất đã biết để đi tiếp.
🧮 Các bước thực hiện
Giả sử đồ thị có:
-
Tập đỉnh: V
-
Trọng số các cạnh: w(u,v)
Bước 1 – Khởi tạo:
-
Gán khoảng cách từ đỉnh nguồn ss đến chính nó là 0, tất cả các đỉnh khác là ∞
-
Đánh dấu tất cả các đỉnh là chưa được thăm
-
Tạo tập đỉnh Q chứa tất cả các đỉnh
Bước 2 – Lặp:
-
Trong khi QQ chưa rỗng:
-
Chọn đỉnh u∈Qu \in Q có khoảng cách nhỏ nhất
-
Đánh dấu uu là đã thăm, loại khỏi QQ
-
Với mỗi đỉnh kề vv của uu, nếu đường đi qua uu ngắn hơn:
Neˆˊu dist[u]+w(u,v)<dist[v] thıˋ cập nhật dist[v
-
✅ Ví dụ minh họa nhỏ
Giả sử đồ thị:
Các cạnh:
-
AB = 1
-
AD = 2
-
BD = 1
-
BC = 4
Tìm đường đi ngắn nhất từ A đến các đỉnh khác.
Khởi tạo:
Lặp:
-
Chọn A (0):
-
B: 0+1 = 1 → cập nhật dist[B] = 1
-
D: 0+2 = 2 → cập nhật dist[D] = 2
-
-
Chọn B (1):
-
D: 1+1 = 2 (không đổi)
-
C: 1+4 = 5 → dist[C] = 5
-
-
Chọn D (2): không cải thiện gì
-
Chọn C (5): xong
Kết quả:
🛠 Ứng dụng thực tế
-
GPS tìm đường đi ngắn nhất
-
Lập trình game (AI di chuyển)
-
Mạng máy tính, định tuyến (routing protocols)
🎁 Tải Tài Liệu Ôn Thi & Mở Khóa Trọn Bộ Đề Tủ Toán Lớp 5 – Lớp 6 & Ôn Vào 6 CLC (2026–2027)
Biên soạn & kiểm duyệt bởi ThS. Nguyễn Thế Anh (Á khoa ĐH Ngoại thương & ĐH Y Hà Nội • 2 Điểm 10 Toán)
📥 Nhận Bản PDF Đề In Sắc Nét + Phác Đồ Rà Lỗ Hổng 8 Tuần
Điền SĐT Zalo để hệ thống gửi ngay file PDF chuẩn in + tư vấn lộ trình học sát lực học hiện tại của con:
9986683218 – Nguyễn Thế Anh📝 Nội dung CK:
TTA PDF HK1T6 + SĐT Zalo
Phụ huynh & học sinh đang tìm lớp Toán nhóm nhỏ kèm sát theo đúng lực học, mục tiêu và khu vực có thể xem chi tiết lộ trình tại:
- 🏫 Lớp học thêm Toán uy tín tại Hà Nội & Zoom trực tuyến (Lớp 6 – Lớp 12)
- 📍 Lớp học thêm Toán Quận Hai Bà Trưng (Ngõ 230 Lạc Trung – Gần Minh Khai, Times City)
- 🌿 Lớp học thêm Toán tại KĐT Ecopark & Văn Giang (111 Vạn Tuế – Toán Phổ thông & Cambridge)
- 🚀 Lớp luyện thi Toán Đánh giá năng lực HSA, TSA & Chinh phục 9+ Tốt nghiệp THPT
- 🏆 Lớp luyện thi Toán vào lớp 10, Toán Chuyên Ngữ / Chuyên XHNV & Toán Quốc tế Cambridge
- 🆕 Bài Toán Tối Ưu Hoá Thực Tế Đạo Hàm (Toán 12), Tư Duy Định Lượng HSA & Chiến Lược Quy Đổi Điểm Bách Phân Vị
- 🆕 Phương Pháp Gắn Hệ Trục Toạ Độ Không Gian Oxyz, Đọc Hiểu Khoa Học TSA & Công Thức Điểm Xét Tuyển BCA 60–40
- 🆕 TỔNG HỢP CÔNG THỨC & KIẾN THỨC CỐT LÕI TOÁN 7
- 🆕 Lộ trình học chuẩn Toán 7 theo năm học (Chương trình GDPT mới)
- 👉 Xem toàn bộ Kho Đề Thi Giữa Kì, Học Kì & Công Thức Toán Lớp 6–12 →
