07.1 - Đường đi ngắn nhất trên đồ thị không trọng số

Giới thiệu

Đường đi ngắn nhất là một trong những bài toán kinh điển trong lý thuyết đồ thị và cũng có nhiều ứng dụng trong thực tiễn. Ví dụ như đường đi ngắn nhất giữa hai địa điểm trong thành phố với giả đỉnh mỗi ngã ba, ngã tư là một đỉnh và các cung đường là cạnh. Hay bài toán tìm đường ngắn nhất để chuyển gói tin trong mạng, ...

Đối với bài toán tìm đường đi ngắn nhất xuất phát từ một nguồn, ta dễ dàng thực hiện hiện bằng giải thuật BFS với độ phức tạp O(V+E) với đồ thị không trọng số được lưu bằng danh sách kề. Đối với độ thị có trọng số, BFS không cho kết quả đúng vì có khả năng đường đi qua nhiều cạnh nhưng tổng trọng số lại nhỏ hơn đường đi qua ít cạnh hơn. Lúc này cần dùng đến các thuật toán Dijkstra với độ phức tạp O((V+E)*logV) hay Bellman-Ford với độ phức tạp O(VE) tùy theo đồ thị có chứa cạnh có trọng số âm hay không.

Trong chủ đề này, chúng ta sẽ thảo luận qua các bài toán tìm đường đi ngắn nhất trên đồ thị không trọng số và có trọng số với các biến thể khác nhau của chúng.

Tài liệu tham khảo

• Competitive Programming 4, Steven Halim

• Tài liệu giáo khoa chuyên Tin 1, Hồ Sỹ Đàm

• GeeksforGeeks

Độ thị không trọng số

Đường đi ngắn nhất từ một nguồn đến một đích (Single-Source Single-Destination - SSSDSP)

Đối với bài toán này, ta không cần tìm đường đi ngắn nhất từ nguồn s đến tất cả các đỉnh mà chỉ cần tới một đỉnh t duy nhất, nên trong quá trình pop up từ hàng đợi ra, nếu ta gặp t thì thoát ngay vòng lặp. Trong trường hợp xấu nhất, tức là ta nằm ở lớp cuối cùng trong cây BFS thì độ phức tạp là O(V+E), đa số trường hợp khác sẽ chạy nhanh hơn.

Đường đi ngắn nhất từ  nhiều nguồn đến một đích (Single - Destination Shortest Paths - SDSP)

Nhiều bài toán yêu cầu tìm đường đi ngắn nhất từ nhiều nguồn đến một đích duy nhất. Thay vì chạy BFS nhiều lần, ta có thể đảo chiều đồ thị rồi chạy BFS qua một lần duy nhất.

Đường đi ngắn nhất từ nhiều nguồn (Multi Source Shortest Paths - MSSP)

Một số bài toán yêu cầu tìm đường đi ngắn nhất từ nhiều nguồn đến tất cả các đỉnh khác. Ví dụ yêu cầu cần tìm đường đi ngắn nhất từ K nguồn, rõ ràng với giải thuật BFS thông thường, ta phải thực hiện với độ phức tạp O(K(V+E)), trong trường hợp lớn nhất K có thể bằng V.

Để giảm độ phức tạp cho bài toán này, ta có thể sử dụng một trong hai kỹ thuật sau đây:

Cách 1. Đẩy tất cả các nguồn s vào hàng đợi, dùng một mảng dist[] và khởi tạo tất cả dist[s] = 0 trước khi chạy BFS --> như vậy BFS cũng chỉ chạy một lần.

Cách 2. Tạo ra một đỉnh giả là đỉnn zero nối tới các nguồn s và đặt chi phí cho các cung nối từ đỉnh zero đến các đỉnh s là 0. Sau đó thực hiện BFS bình thường từ đỉnh Zero.

Đoạn code sau đây minh họa cho cách thứ nhất:

Đồ thì trọng số 0/1 ( On 0/1 weighted Graph)

Đây là một biến thể khác của bài toán tìm đường đi ngắn nhất trên độ thị không trọng số. Giá trị 0/1 ở đây chỉ chi phí khác nhau cho hai loại đường đi. Bài toán được mô tả chi tiết như sau:

Cho một đồ thị lưới mà mỗi ô có thể chứa các chữ cái in hoa từ 'A'-'Z' hay các dầu '.' hay các dấu '#'. Chúng ta chỉ có thể di chuyển qua các ô chưa chữ cái hoặc dấu '.'. Biết rằng việc di chuyển qua các chữ cái tốn chi phí 0 và di chuyển qua các dấu '.' tốn chi phí 1.

Yêu cầu: xác định đường đi ngắn nhất từ một ký tự 'A' bất kỳ đến một ký tự 'B'

Nhiệm vụ 1. Cài đặt hoàn chỉnh bài toán đồ thị trọng số 0/1 ở trên. Với định dạng input, output như sau:

Input: 

• Dòng đầu tiên chứa hai số nguyên N, M là kích thước lưới.

• N dòng tiếp theo, mỗi dòng chứa M ký tự thuộc một trong ba loại: chữ cái in hoa, dấu '.', dấu '#'

Output:

• Một số nguyên duy nhất là đường đi ngắn nhất từ một ký tự 'A' đến một ký tự 'B'

Nhiệm vụ 2. UVa 00336 - A Node Too Far

Nhiệm vụ 3. UVa 16643 - Knight Tour