Học thử miễn phí
Bài học PremiumTin học 12 HSG — Đường đi ngắn nhất và cây khung nhỏ nhất
Bảy bài học đi từ Dijkstra, Bellman-Ford/SPFA, Floyd-Warshall đến DSU, Kruskal, Prim, khép lại bằng một đề mini tổng hợp — mọi thuật toán đều được cài đặt bằng Python (heapq), chứng minh đúng đắn bằng phản ví dụ và tính chất lát cắt, và đối chiếu số liệu thực nghiệm khi chọn cài đặt theo mật độ đồ thị.
7 chương7 phầnKhoảng 11,2 giờ
Học Chương 1 miễn phíNội dung bài học
Chương 1 mở xem thử, các chương còn lại nằm trong gói Premium.
Dijkstra — đường đi ngắn nhất trọng số không âm
Bellman–Ford và SPFA — đồ thị có cạnh trọng số âm
- Bellman-Ford, SPFA và phát hiện chu trình âm75 phútPremium
Floyd–Warshall — đường đi ngắn nhất giữa mọi cặp đỉnh
- Floyd-Warshall — DP mọi cặp đỉnh70 phútPremium
DSU (Union–Find) — hợp nhất và nén đường
- DSU — hợp nhất tập hợp với nén đường và hợp nhất theo hạng60 phútPremium
Kruskal — cây khung nhỏ nhất bằng DSU
- Kruskal — cây khung nhỏ nhất bằng DSU70 phútPremium
Prim — cây khung nhỏ nhất bằng heap
- Prim — bản mảng và bản heap, chọn theo mật độ cạnh70 phútPremium
Đề kiểm tra tổng hợp — đường đi ngắn nhất và cây khung nhỏ nhất
- Đề mini tổng hợp — chọn đúng thuật toán theo ràng buộc70 phútPremium