| Bước | Đỉnh đang xét | dist(A) | dist(B) | dist(C) | dist(D) | Tập đã xét | |------|---------------|---------|---------|---------|---------|-------------| | 0 | Khởi tạo | 0 | ∞ | ∞ | ∞ | {} | | 1 | A | 0 | (A→B) | 2 (A→C) | ∞ | A | | 2 | C (chọn C vì dist=2 nhỏ nhất) | 0 | min(5, 2+3=5) →5 | 2 | 2+7=9 | A, C | | 3 | B (chọn B vì dist=5) | 0 | 5 | 2 | min(9, 5+1=6) → 6 | A, C, B | | 4 | D | 0 | 5 | 2 | 6 | A, C, B, D |
Để xem thêm các bài tập và mã nguồn mẫu, bạn có thể tham khảo tại hoặc các tài liệu chuyên sâu trên
Cho đồ thị có hướng (hoặc vô hướng) với các trọng số không âm như sau (ma trận kề hoặc danh sách cạnh):
Cho đồ thị: A → B (trọng số 4), A → C (trọng số 2), C → B (trọng số -3). Hãy chạy Dijkstra từ A và giải thích tại sao kết quả sai. bai tap thuat toan dijkstra co loi giai
Thuật toán duyệt các đỉnh theo chiến lược tham lam (Greedy). Tại mỗi bước, nó chọn đỉnh có khoảng cách nhỏ nhất từ nguồn mà chưa được duyệt, sau đó cập nhật khoảng cách đến các đỉnh kề với nó (quá trình gọi là Relaxation - đơn giản hóa cạnh).
Dưới đây là bài tập mẫu về thuật toán Dijkstra cùng lời giải chi tiết theo từng bước để bạn dễ dàng theo dõi và thực hành. Bài tập: Tìm đường đi ngắn nhất
là một trong những thuật toán nổi tiếng nhất trong lý thuyết đồ thị, dùng để 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 trên đồ thị có trọng số không âm. Để nắm vững thuật toán này, không có cách nào tốt hơn là thực hành qua các bài tập thuật toán Dijkstra có lời giải . | Bước | Đỉnh đang xét | dist(A)
Bạn cần mình giải thêm bài nào hoặc cung cấp code mẫu không?
Cho đồ thị có hướng: 1→2 (2), 1→3 (4), 2→3 (1), 2→4 (7), 3→5 (3), 4→5 (1), 5→4 (2). Tìm đường từ 1 đến 4.
Trước khi bắt tay vào giải bài tập, hãy cùng ôn lại các bước chính của thuật toán Dijkstra: Tại mỗi bước, nó chọn đỉnh có khoảng
Tìm đường đi ngắn nhất từ A đến C.
Cho một đồ thị có hướng với các trọng số dương như sau: