Học thử miễn phí
Tin 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 bài họcKhoảng 11.2 giờ
Học miễn phí trong ứng dụngNội dung khóa học
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
Floyd–Warshall — đường đi ngắn nhất giữa mọi cặp đỉnh
DSU (Union–Find) — hợp nhất và nén đường
Kruskal — cây khung nhỏ nhất bằng DSU
Prim — cây khung nhỏ nhất bằng heap
Đề kiểm tra tổng hợp — đường đi ngắn nhất và cây khung nhỏ nhất