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

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ư định tuyến mạng, tìm đường đi tối ưu trong bản đồ, và phân tích mạng xã hội.

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) nối giữa các đỉnh. Đường đi trong đồ thị là một dãy các đỉnh liên tiếp được nối với nhau 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. Tùy thuộc vào loại trọng số, chúng ta có các thuật toán khác nhau để giải bài toán này.

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.

Các bước thực hiện thuật toán Dijkstra:

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, trừ đỉnh nguồn có khoảng cách là 0.
2. Chọn đỉnh chưa được thăm có khoảng cách ngắn nhất từ đỉnh nguồn.
3. Cập nhật khoảng cách của các đỉnh lân cận của đỉnh đã chọn.
4. Đánh dấu đỉnh đã chọn là đã được thăm.
5. Lặp lại các bước 2-4 cho đến khi tất cả các đỉnh đều đượ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 cao hơn thuật toán Dijkstra.

Các bước thực hiện thuật toán Bellman-Ford:

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, 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ị):
• Duyệt qua tất cả các cạnh trong đồ thị.
• Nếu khoảng cách từ đỉnh nguồn đến đỉnh đầu của cạnh cộng với trọng số của cạnh nhỏ hơn khoảng cách từ đỉnh nguồn đến đỉnh cuối của cạnh, thì cập nhật khoảng cách của đỉnh cuối của cạnh.
3. Kiểm tra xem có chu trình âm trong đồ thị hay không. Nếu có chu trình âm, thì bài toán không có nghiệm.

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

Bài toán tìm đường đi ngắn nhất có nhiều ứng dụng thực tế trong các lĩnh vực khác nhau:

• Định tuyến mạng: Tìm đường đi ngắn nhất giữa hai máy tính trong mạng.
• Tìm đường đi tối ưu trong bản đồ: Tìm đường đi ngắn nhất giữa hai địa điểm trên bản đồ.
• 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.
• Lập kế hoạch vận tải: Tìm đường đi ngắn nhất cho các phương tiện vận tải.

6. Bài tập vận dụng

Để 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 giữa hai đỉnh trong một đồ thị cho trước bằng thuật toán Dijkstra.
• Tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị cho trước bằng thuật toán Bellman-Ford.
• Giải các bài toán thực tế liên quan đến bài toán tìm đường đi ngắn nhất.

Hy vọng bài học này đã cung cấp cho bạn những kiến thức hữu ích về bài toán tìm đường đi ngắn nhất. Chúc bạn học tập tốt!