Bài 3. Bài toán tìm đường đi ngắn nhất

Bài 3. Bài toán tìm đường đi ngắn nhất - Chuyên đề học tập Toán 11 - Chân trời sáng tạo Chuyên đề 2. Lí thuyết đồ thị

Bài toán tìm đường đi ngắn nhất là một trong những bài toán cơ bản và quan trọng trong lĩnh vực lý thuyết đồ thị. Bài toán này có nhiều ứng dụng thực tế trong các lĩnh vực như mạng máy tính, giao thông vận tải, và logistics.

1. Giới thiệu về đồ thị và đường đi

Trước khi đi sâu vào bài toán tìm đường đi ngắn nhất, chúng ta cần hiểu rõ về khái niệm đồ thị. Đồ thị là một cấu trúc dữ liệu bao gồm các đỉnh (vertices) và các cạnh (edges). Các cạnh kết nối các đỉnh với nhau. Đường đi trong đồ thị là một dãy các đỉnh liên tiếp được kết nối bởi các cạnh.

2. Bài toán tìm đường đi ngắn nhất

Bài toán tìm đường đi ngắn nhất là tìm đường đi giữa hai đỉnh cho trước trong đồ thị sao cho tổng trọng số của các cạnh trên đường đi là nhỏ nhất. Trọng số của cạnh có thể là dương, âm hoặc không. Có nhiều thuật toán khác nhau để giải bài toán này, tùy thuộc vào đặc điểm của đồ thị.

3. Thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán phổ biến để tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác trong đồ thị có trọng số không âm. Thuật toán này hoạt động bằng cách duy trì một tập hợp các đỉnh đã được thăm và một tập hợp các đỉnh chưa được thăm. Tại mỗi bước, thuật toán chọn đỉnh chưa được thăm có khoảng cách ngắn nhất từ đỉnh nguồn và cập nhật khoảng cách của các đỉnh lân cận.

1. Khởi tạo khoảng cách từ đỉnh nguồn đến tất cả các đỉnh khác là vô cùng.
2. Đặt khoảng cách từ đỉnh nguồn đến chính nó là 0.
3. Chọn đỉnh chưa được thăm có khoảng cách ngắn nhất từ đỉnh nguồn.
4. Cập nhật khoảng cách của các đỉnh lân cận của đỉnh đã chọn.
5. Lặp lại các bước 3 và 4 cho đến khi tất cả các đỉnh đã được thăm.

4. Thuật toán Bellman-Ford

Thuật toán Bellman-Ford là một thuật toán tổng quát hơn thuật toán Dijkstra, có thể giải bài toán tìm đường đi ngắn nhất trong đồ thị có trọng số âm. Tuy nhiên, thuật toán Bellman-Ford có độ phức tạp thời gian cao hơn thuật toán Dijkstra.

Thuật toán Bellman-Ford hoạt động bằng cách lặp đi lặp lại qua tất cả các cạnh của đồ thị và cập nhật khoảng cách của các đỉnh lân cận. Sau khi lặp lại n-1 lần (n là số lượng đỉnh trong đồ thị), thuật toán sẽ tìm ra đường đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh khác.

5. Ứng dụng của bài toán tìm đường đi ngắn nhất

• Mạng máy tính: Tìm đường đi ngắn nhất giữa hai máy tính trong mạng.
• Giao thông vận tải: Tìm đường đi ngắn nhất giữa hai địa điểm trên bản đồ.
• Logistics: Tìm đường đi ngắn nhất để vận chuyển hàng hóa.
• Robot học: Lập kế hoạch đường đi cho robot.

6. Ví dụ minh họa

Xét đồ thị sau:

Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh D bằng thuật toán Dijkstra:

1. Khởi tạo khoảng cách: A=0, B=∞, C=∞, D=∞, E=∞, F=∞
2. Chọn A: Cập nhật B=4, C=2
3. Chọn C: Cập nhật E=5
4. Chọn B: Cập nhật D=14
5. Chọn E: Cập nhật D=9
6. Kết quả: Đường đi ngắn nhất từ A đến D là A -> C -> E -> D với tổng trọng số là 9.

7. Bài tập luyện tập

Để củng cố kiến thức về bài toán tìm đường đi ngắn nhất, bạn có thể thực hành các bài tập sau:

• Tìm đường đi ngắn nhất từ đỉnh A đến đỉnh F trong đồ thị trên.
• Xây dựng một đồ thị và áp dụng thuật toán Dijkstra để tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ.
• Nghiên cứu và so sánh các thuật toán tìm đường đi ngắn nhất khác nhau.

Chúc bạn học tập tốt!