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ý thuyết đồ thị, có ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học máy tính, vận tải, mạng lưới truyền thông,… Trong bài viết này, chúng ta sẽ đi sâu vào phân tích và giải quyết bài toán này trong chương trình Toán 11 Chân trời sáng tạo.

1. Giới thiệu về Lý thuyết đồ thị

Trước khi đi vào bài toán cụ thể, chúng ta cần nắm vững một số khái niệm cơ bản về lý thuyết đồ 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) nối giữa các đỉnh.
• Đỉnh: Đại diện cho một đối tượng hoặc một vị trí.
• Cạnh: Đại diện cho mối quan hệ giữa hai đỉnh. Cạnh có thể có hướng (directed edge) hoặc không hướng (undirected edge).
• Trọng số cạnh: Một số thực gán cho mỗi cạnh, biểu thị chi phí hoặc khoảng cách giữa hai đỉnh.
• Đường đi: Một dãy các đỉnh liên tiếp nhau bằng các cạnh.
• Đường đi đơn giản: Một đường đi không lặp lại bất kỳ đỉnh nào.
• Chu trình: Một đường đi bắt đầu và kết thúc tại cùng một đỉ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 một đồ thị sao cho tổng trọng số các cạnh trên đường đi là nhỏ nhất.

Có hai loại bài toán tìm đường đi ngắn nhất phổ biến:

• Bài toán đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh khác: Tìm đường đi ngắn nhất từ một đỉnh nguồn (source vertex) đến tất cả các đỉnh còn lại trong đồ thị.
• Bài toán đường đi ngắn nhất giữa hai đỉnh cho trước: Tìm đường đi ngắn nhất giữa hai đỉnh cụ thể trong đồ thị.

3. Thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán phổ biến để giải bài toán đườ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.

Nguyên lý hoạt động:

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 (infinity), trừ đỉnh nguồn có khoảng cách là 0.
2. Chọn đỉnh chưa được xét có khoảng cách nhỏ nhất.
3. Cập nhật khoảng cách từ đỉnh đã chọn đến các đỉnh lân cận. Nếu khoảng cách mới nhỏ hơn khoảng cách hiện tại, thì cập nhật lại.
4. Lặp lại bước 2 và 3 cho đến khi tất cả các đỉnh đều được xét.

4. Thuật toán Bellman-Ford

Thuật toán Bellman-Ford có thể giải bài toán đườ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ố âm hoặc không âm. Tuy nhiên, thuật toán này sẽ phát hiện ra các chu trình âm (negative cycle) trong đồ thị, khi đó bài toán không có nghiệm.

Nguyên lý hoạt động:

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 (infinity), trừ đỉnh nguồn có khoảng cách là 0.
2. Lặp lại V-1 lần (V là số đỉnh trong đồ thị). Trong mỗi lần lặp, duyệt qua tất cả các cạnh và cập nhật khoảng cách từ đỉnh đầu của cạnh đến đỉnh cuối của cạnh. Nếu khoảng cách mới nhỏ hơn khoảng cách hiện tại, thì cập nhật lại.
3. Kiểm tra xem có chu trình âm hay không. Nếu có, thì thông báo rằng bài toán không có nghiệm.

5. Ví dụ minh họa

Xét đồ thị có 5 đỉnh A, B, C, D, E và các cạnh có trọng số như sau:

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

Kết quả: Đường đi ngắn nhất từ A đến E là A -> C -> E, với tổng trọng số là 2 + 3 = 5.

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

• Định tuyến trong mạng lưới giao thông: Tìm đường đi ngắn nhất giữa hai địa điểm trên bản đồ.
• Tìm đường đi ngắn nhất trong mạng lưới truyền thông: Tìm đường đi ngắn nhất giữa hai máy tính trong mạng.
• Lập kế hoạch sản xuất: Tìm đường đi ngắn nhất để hoàn thành một quy trình sản xuất.
• Phân tích mạng xã hội: Tìm đường đi ngắn nhất giữa hai người dùng trong mạng xã hội.

Hy vọng bài viết này đã cung cấp cho các em những kiến thức cơ bản và hữu ích về bài toán tìm đường đi ngắn nhất trong chương trình Toán 11 Chân trời sáng tạo. Chúc các em học tập tốt!