Loigiai.com.vn - 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 giao thông,... Bài viết này sẽ trình bày chi tiết về bài toán này, bao gồm định nghĩa, các thuật toán phổ biến và ví dụ minh họa.

1. Định nghĩa bài toán tìm đường đi ngắn nhất

Cho một đồ thị có trọng số G = (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh. Mỗi cạnh e ∈ E có một trọng số w(e) là một số thực không âm. Bài toán tìm đường đi ngắn nhất giữa hai đỉnh s và t trong đồ thị G là tìm đường đi từ s đến t sao cho tổng trọng số các cạnh trên đường đi là nhỏ nhất.

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

Có nhiều thuật toán khác nhau để giải bài toán tìm đường đi ngắn nhất, trong đó phổ biến nhất là:

Thuật toán Dijkstra: Thuật toán này 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 Bellman-Ford: Thuật toán này 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ị, kể cả đồ thị có trọng số âm (nhưng không có chu trình âm).
Thuật toán Floyd-Warshall: Thuật toán này tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị.

3. Thuật toán Dijkstra - Giải thích chi tiết

Thuật toán Dijkstra hoạt động dựa trên nguyên tắc tham lam. Nó bắt đầu từ đỉnh nguồn và lặp đi lặp lại việc chọn đỉnh chưa được thăm có khoảng cách ngắn nhất từ đỉnh nguồn, sau đó cập nhật khoảng cách đến các đỉnh lân cận của đỉnh đó.

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

Khởi tạo: Đặt khoảng cách từ đỉnh nguồn đến chính nó bằng 0, và khoảng cách từ đỉnh nguồn đến tất cả các đỉnh khác bằng vô cùng.
Lặp: Lặp lại cho đến khi tất cả các đỉnh đều được thăm:

Chọn đỉnh chưa được thăm có khoảng cách ngắn nhất từ đỉnh nguồn.
Đánh dấu đỉnh này là đã được thăm.
Cập nhật khoảng cách đến các đỉnh lân cận của đỉnh này: Nếu khoảng cách từ đỉnh nguồn đến đỉnh lân cận thông qua đỉnh hiện tại ngắn hơn khoảng cách hiện tại đến đỉnh lân cận, thì cập nhật khoảng cách.

4. Ví dụ minh họa

Xét đồ thị sau:

0 4 2 ∞ 4 0 5 10 2 5 0 3 ∞ 10 3 0

Đỉnh	A	B	C	D
A
B
C
D

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

Bắt đầu từ đỉnh A, khoảng cách đến A là 0, đến B là 4, đến C là 2, đến D là vô cùng.

Chọn đỉnh C (khoảng cách ngắn nhất là 2). Cập nhật khoảng cách đến các đỉnh lân cận của C: Khoảng cách từ A đến D thông qua C là 2 + 3 = 5, nhỏ hơn vô cùng, nên cập nhật khoảng cách đến D là 5.

Chọn đỉnh B (khoảng cách ngắn nhất là 4). Cập nhật khoảng cách đến các đỉnh lân cận của B: Khoảng cách từ A đến D thông qua B là 4 + 10 = 14, lớn hơn 5, nên không cập nhật.

Chọn đỉnh D (khoảng cách ngắn nhất là 5). Đã tìm được đường đi ngắn nhất từ A đến D với khoảng cách là 5.

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

Đị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 máy tính: 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 cách sản xuất sản phẩm với chi phí thấp nhấ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. Chúc các em học tập tốt!