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

1. Giới thiệu chung về 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à một bài toán cơ bản trong lý thuyết đồ thị, có ứng dụng rộng rãi trong nhiều lĩnh vực như định tuyến mạng, tìm đường đi trong bản đồ, và phân tích mạng xã hội. Mục tiêu của bài toán là tìm đường đi có tổng trọng số cạnh nhỏ nhất giữa hai đỉnh cho trước trong một đồ thị.

2. Các thuật toán tìm đường đi ngắn nhất

2.1. Thuật toán Dijkstra

Thuật toán Dijkstra là một thuật toán tham lam, được sử dụng để 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 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.

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

2.2. 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ể được sử dụng để 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 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.

1. Bước 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. Bước 2: Lặp lại qua tất cả các cạnh của đồ thị V-1 lần, trong đó V là số lượng đỉnh trong đồ thị.
3. Bước 3: Tại mỗi cạnh (u, v) với trọng số w, kiểm tra xem khoảng cách từ đỉnh nguồn đến đỉnh u cộng với w có nhỏ hơn khoảng cách từ đỉnh nguồn đến đỉnh v hay không. Nếu có, cập nhật khoảng cách của đỉnh v.
4. Bước 4: Sau khi lặp lại V-1 lần, lặp lại qua tất cả các cạnh của đồ thị một lần nữa. Nếu bất kỳ khoảng cách nào vẫn được cập nhật, điều đó có nghĩa là đồ thị chứa một chu trình âm.

3. Ứ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ế, bao gồm:

• Định tuyến mạng: Tìm đường đi ngắn nhất giữa hai máy tính trong một mạng.
• Tìm đường đi 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ột mạng xã hội.
• Lập kế hoạch vận tải: Tìm đường đi ngắn nhất cho một xe tải để giao hàng đến nhiều địa điểm.

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

Dưới đây là một số bài tập vận dụng để giúp bạn hiểu rõ hơn về bài toán tìm đường đi ngắn nhất:

1. Cho một đồ thị có 5 đỉnh và các cạnh có trọng số như sau: (1, 2, 3), (1, 3, 5), (2, 3, 2), (2, 4, 6), (3, 4, 1), (3, 5, 4), (4, 5, 2). Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 5 bằng thuật toán Dijkstra.
2. Cho một đồ thị có 4 đỉnh và các cạnh có trọng số như sau: (1, 2, -2), (2, 3, -3), (3, 4, -1), (4, 1, -4). Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 4 bằng thuật toán Bellman-Ford.

5. Kết luận

Bài 3. Bài toán tìm đường đi ngắn nhất là một bài toán quan trọng trong lý thuyết đồ thị, có ứng dụng rộng rãi trong nhiều lĩnh vực. Việc nắm vững các thuật toán tìm đường đi ngắn nhất sẽ giúp bạn giải quyết nhiều bài toán thực tế một cách hiệu quả.