Thuật toán Dijkstra là một trong những thuật toán quan trọng nhất trong khoa học máy tính, được sử dụng rộng rãi để tìm đường đi ngắn nhất giữa hai điểm trên một đồ thị. Trong bài viết này, chúng ta sẽ cùng tìm hiểu về thuật toán Dijkstra thông qua các bài tập có lời giải chi tiết.
Hiểu Rõ Về Thuật Toán Dijkstra
Trước khi đi vào các bài tập, hãy cùng ôn lại một số khái niệm cơ bản:
- Đồ thị: Là một tập hợp các đỉnh (node) và các cạnh (edge) nối giữa chúng.
- Trọng số: Mỗi cạnh trong đồ thị có thể có một trọng số (weight) thể hiện chi phí di chuyển trên cạnh đó.
- Đường đi ngắn nhất: Là đường đi giữa hai đỉnh có tổng trọng số các cạnh nhỏ nhất.
Thuật toán Dijkstra hoạt động dựa trên nguyên lý tham lam, luôn chọn đường đi có chi phí thấp nhất tại mỗi bước. Thuật toán bắt đầu từ đỉnh nguồn, tính toán khoảng cách ngắn nhất đến tất cả các đỉnh còn lại trong đồ thị.
Bài Tập 1: Tìm Đường Đi Ngắn Nhất
Cho đồ thị như hình vẽ, hãy tìm đường đi ngắn nhất từ đỉnh A đến đỉnh F bằng thuật toán Dijkstra:
Lời giải:
- Khởi tạo:
- Gán khoảng cách từ đỉnh A đến chính nó là 0, các đỉnh còn lại là vô cùng.
- Tạo một tập hợp các đỉnh đã được xét (ban đầu chỉ chứa đỉnh A).
- Lặp:
- Chọn đỉnh chưa được xét có khoảng cách nhỏ nhất từ đỉnh A.
- Cập nhật khoảng cách đến các đỉnh kề với đỉnh vừa chọn, nếu khoảng cách mới nhỏ hơn khoảng cách cũ.
- Thêm đỉnh vừa xét vào tập hợp các đỉnh đã được xét.
- Kết thúc: Khi tất cả các đỉnh đã được xét, ta thu được đường đi ngắn nhất từ A đến F.
Bảng minh họa:
| Bước | Đỉnh được chọn | Khoảng cách | Đỉnh đã xét |
|---|---|---|---|
| 1 | A | A=0 | A |
| 2 | B | A=0, B=2 | A, B |
| 3 | C | A=0, B=2, C=5 | A, B, C |
| 4 | D | A=0, B=2, C=5, D=7 | A, B, C, D |
| 5 | E | A=0, B=2, C=5, D=7, E=9 | A, B, C, D, E |
| 6 | F | A=0, B=2, C=5, D=7, E=9, F=11 | A, B, C, D, E, F |
Vậy đường đi ngắn nhất từ A đến F là A -> B -> D -> F với tổng trọng số là 11.
Bài Tập 2: Ứng Dụng Thực Tế
Một công ty vận chuyển muốn tìm tuyến đường ngắn nhất để vận chuyển hàng hóa từ kho hàng đến các cửa hàng. Biết khoảng cách giữa các địa điểm như sau:
Hãy sử dụng thuật toán Dijkstra để giúp công ty tìm tuyến đường ngắn nhất từ kho hàng (K) đến từng cửa hàng (C1, C2, C3).
Lời giải:
Bài tập này có thể được giải quyết tương tự như bài tập 1. Bằng cách áp dụng thuật toán Dijkstra, ta có thể tìm được đường đi ngắn nhất từ kho hàng đến từng cửa hàng.
Kết Luận
Bài viết đã giới thiệu về thuật toán Dijkstra và cách giải các bài tập cơ bản. Thuật toán Dijkstra là một công cụ mạnh mẽ có thể được ứng dụng trong nhiều lĩnh vực khác nhau, từ định tuyến mạng đến lập kế hoạch di chuyển.
FAQs
1. Thuật toán Dijkstra có thể áp dụng cho đồ thị có trọng số âm?
Không, thuật toán Dijkstra không hoạt động chính xác với đồ thị có trọng số âm.
2. Độ phức tạp của thuật toán Dijkstra là bao nhiêu?
Độ phức tạp thời gian của thuật toán Dijkstra phụ thuộc vào cách cài đặt, có thể là O(V^2) hoặc O(E + V log V), trong đó V là số đỉnh và E là số cạnh.
Bạn Cần Hỗ Trợ?
Liên hệ ngay với chúng tôi:
- Số Điện Thoại: 02033846993
- Email: [email protected]
- Địa chỉ: X2FW+GGM, Cái Lân, Bãi Cháy, Hạ Long, Quảng Ninh, Việt Nam
Đội ngũ Giải Bóng luôn sẵn sàng hỗ trợ bạn 24/7!