Bài toán tìm đường đi ngắn nhất
Cách tìm đường đi ngắn nhất trong đồ thị có trọng số
Bài toán tìm đường đi ngắn nhất là một trong những nội dung quan trọng của chuyên đề Lý thuyết đồ thị Toán 11. Không chỉ xuất hiện trong các bài tập học thuật, dạng toán này còn có nhiều ứng dụng thực tiễn như tìm đường trên bản đồ, tối ưu mạng lưới giao thông và hệ thống vận chuyển. Cùng tìm hiểu phương pháp giải, các dạng bài tập thường gặp và lời giải chi tiết trong bài viết dưới đây.
Bài toán tổng quát
Để giải quyết bài toán tìm đường đi ngắn nhất nối A với F, chúng ta sẽ xem sơ đồ đã cho như một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, số đó chính là độ dài của con đường. Những đồ thị như vậy gọi là đồ thị có trọng số và con số được gắn với một cạnh gọi là trọng số của cạnh đó. Bài toán đã cho trở thành tìm một đường đi từ A đến F với tổng các trọng số nhỏ nhất, tức là cần xác định nhãn vĩnh viễn I(F).
Đồ thị có trọng số là một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, gọi là trọng số củacạnh đó. Để tìm đường đi ngắn nhất từ đỉnh A đến đỉnh F của một đồ thị có trọng số, ta xuất phát từ đỉnh A và di chuyển theo các cạnh của đồ thị. Với mỗi đỉnh V, ta gắn một số I(V) là khoảng cách ngắn nhất để đi từ A đến V gọi là nhãn vỉnh viễn của đỉnh V. Như vậy, để tìm độ dài của đường đi ngắn nhất nối A với F thìta cần tìm 
\(I(F)\).
Ví dụ: Cho sơ đồ như hình vẽ, \(A, B, C, D, E; F\) là các địa điểm nối với nhau bới các con đường với độ dài của mỗi con đường kí hiệu trên hình.
a) Hãy chỉ ra 2 con đường đi từ A đến F và so sánh độ dài của hai đường đi đó.
b) Với mỗi đỉnh V của sơ đô trên, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy ta có ngay \(I(A) = 0\). Dựa vào sơ đồ hãy tìm các nhãn vĩnh viễn \(I(B), I(C)\) của hai đỉnh kề với A là B, C.
c) Tìm độ dài của đường đi ngắn nhất nối A với F trong đồ thị.
Hướng dẫn giải
a) Hai đường đi từ A đến F là \(ABDF\) và \(ACEF\).
Độ dài đường đi \(ABDF\) là \(3 + 7 + 9 = 19\), độ dài đường đi \(ACEF\) là: \(1 + 5 + 8 = 14\)
Suy ra độ dài \(ABDF\) lớn hơn độ dài \(ACEF\) .
b)\(I(B) = 3; I(C) = 1\)
Để giải quyết bài toán đường đi ngắn nhất nối A với F, chúng ta xem sơ đồ đã cho như một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, số đó chính là độ dài con đường. Những đồ thị như vậy gọi là đồ thị có trọng số và con số được gắn với một cạnh gọi là trọng số của cạnh đó. Bài toán đã cho trở thành tìm một đường đi từ A đến F với tổng các trọng số nhỏ nhất, tức là cần xác định nhãn vĩnh viễn I(F).
c) Ta áp dụng thuật toán đã mô tả:
Đầu tiên ta gắn nhãn đỉnh A là \(I(A) = 0\) và gắn cho 2 đỉnh kề với A là B, C các nhãn tạm thời \(I(A) + 3 = 3; I(A) + 1 = 1\). Chọn số nhỏ nhất cho chúng và viết \(I(C) = 1\). Đỉnh C bây giờ được gắn nhãn vĩnh viễn là 1.
Tiếp theo ta gắn cho các đỉnh kề với C là B, D; E các nhãn tạm thời \(I(C) + 6 = 7; I(C) + 4 = 5\), \(I(C)+5 = 6\) (B hiện nay có hai nhãn tạm thời là 3 và 7). Nhãn tạm thời nhỏ nhất trong các nhãn đã gán (ở \(B, D, E\)) hiện nay là 3 (tại B) nên ta viết \(I(B) = 3\). Đỉnh B được gắn nhãn vĩnh viễn là 3.
Bây giờ ta xét các đỉnh kề với B (Mà chưa được gắn nhãn vĩnh viễn) là D và E. Ta gắn cho đỉnh D nhãn tạm thời \(I(B) + 7= 10\) (D hiện nay có hai nhãn tạm thời là 5 và 10), gắn cho đỉnh E nhãn tạm thời \(I(B) + 2 = 5\) (E có hai nhãn tạm thời là 6 và 5). Nhãn tạm thời nhỏ nhất bây giờ là 5 (tại D và E), do đó ta viết \(I(D) = 5\) và \(I(E) = 5\). Hai đỉnh D và E đều được gắn nhãn vĩnh viễn là 5.
Xét đỉnh kề với D là F, ta gắn cho F nhãn tạm thời \(I(D) + 9 = 14\). Xét đỉnh kề với E là F, ta gắn cho F nhãn tạm thời \(I(E) + 8 = 13\). Vậy đỉnh F sẽ được gắn nhãn vĩnh viễn là 13.
Vì \(I(F) = 13\) nên đường đi ngắn nhất từ A đến F có độ dài là 13.
Để tìm được đi ngắn nhất từ A đền như vậy, ta sẽ lần ngược từ điểm cuối F. Ta chỉ cần giới hạn ở việc xét những cạnh mà độ dài là hiệu của các nhãn gắn tại các đầu mút của nó, đó là \(EF, BE\) và AB (do \(I(F) – I(E) = 13 – 5 = 9\); \(I(E) – I(B) = 5 – 3 = 2\) và \(I(B) – I(A) = 3 – 0 = 3\)). Khi đó ta có thể kết luận, đường đi ngắn nhất từ A đến F phải đi qua các cạnh \(EF, BE; AB\). Vậy đường đi ngắn nhất (trong trường hợp này là duy nhất) từ A đến F là \(A→ B → E → F\).
Chú ý: a) Nếu đồ thị có trọng số mà mỗi cạnh đều có trọng số là 1 thì bài toán trở thành tìm số các cạnh của đường đi ngắn nhất từ A đến F.
b) Các con số trong sơ đồ có thể là thời gian để đi dọc con đường đó, hoặc là chi phí khi đi hết con đường đó. Bởi vậy, ta có thể sử dụng thuật toán giải quyết bài toán gốc về bài toán tìm đường đi ngắn nhất để giải quyết bài toán tìm đường đi nhanh nhất hoặc đường đi có chi phí rẻ nhất.
------------------------
FAQ – Bài Toán Tìm Đường Đi Ngắn Nhất
1. Bài toán tìm đường đi ngắn nhất trong đồ thị là gì?
2. Đường đi ngắn nhất và đường đi đơn có giống nhau không?
Không. Đường đi đơn chỉ yêu cầu không lặp lại đỉnh hoặc cạnh, trong khi đường đi ngắn nhất yêu cầu tổng trọng số nhỏ nhất. Một đường đi ngắn nhất có thể là đường đi đơn nhưng không phải mọi đường đi đơn đều ngắn nhất.
3. Trọng số cạnh trong đồ thị được hiểu như thế nào?
Trọng số cạnh là giá trị biểu diễn khoảng cách, thời gian, chi phí hoặc mức độ liên kết giữa hai đỉnh của đồ thị. Đây là cơ sở để tính toán đường đi tối ưu.
4. Những dạng bài tập tìm đường đi ngắn nhất thường gặp là gì?
Các dạng bài phổ biến gồm:
- Tìm đường đi ngắn nhất giữa hai đỉnh.
- Tính tổng trọng số nhỏ nhất.
- So sánh nhiều lộ trình khác nhau.
- Bài toán tối ưu mạng lưới giao thông.
- Bài toán ứng dụng thực tế bằng đồ thị có trọng số.
----------------
Bài toán tìm đường đi ngắn nhất là chuyên đề quan trọng của Lý thuyết đồ thị Toán 11, giúp học sinh rèn luyện tư duy tối ưu hóa và kỹ năng phân tích dữ liệu. Việc nắm vững lý thuyết, phương pháp giải cùng các dạng bài tập điển hình sẽ giúp các em tự tin hơn khi học tập và vận dụng kiến thức vào thực tế.
