Giải Bài Toán đường đi Ngắn Nhất Bằng Thuật Toán Dijkstra

Đây là hướng dẫn sử dụng thuật toán Dijkstra. Xem thêm:

• Sơ lược về bài toán đường đi ngắn nhất.
• Thuật toán Floyd-Warshall
• Thuật toán Bellman-Ford

Thuật toán Dijkstra là một trong những thuật toán cơ bản dùng để tìm đường đi ngắn nhất từ một điểm tới một điểm nào đó, và mở rộng ra là tìm đường đi ngắn nhất từ 1 điểm tới mọi điểm còn lại của đồ thị, với điều kiện các trọng số của đồ thị đó không âm.

Trước hết, về khâu tổ chức dữ liệu: ta xây dựng một mảng 1D chứa đường đi ngắn nhất giữa đỉnh đang xét tới tất cả các đỉnh còn lại, giá trị ngầm định bằng +INF.

Nói tóm lại, độ phức tạp không gian của thuật toán sẽ là O(V).

Ta xét đồ thị vô hướng sau (số màu đỏ là đường đi ngắn nhất xuất phát từ đỉnh 1 tới đỉnh được xét):

Quá trình thực hiện thuật toán Dijkstra sẽ diễn ra như sau:

• Chọn một điểm bất kỳ chưa được duyệt và có đường đi ngắn nhất từ điểm gốc tới nó là nhỏ nhất.
• Từ điểm đó, loang đường đi ra tất cả các đỉnh kề cận, và cập nhật lại đường đi ngắn nhất tới các đỉnh đó nếu đường đi mới tối ưu hơn.
• Nếu còn điểm chưa được duyệt (hoặc chưa tìm được điểm đích, tùy yêu cầu đề bài), ta trở lại bước 1.

Ta sẽ phân tích tuần tự theo nền tảng ý tưởng này:

Đầu tiên, ta xét đỉnh 1 (vì đường đi ngắn nhất từ 1 tới 1 hiển nhiên có độ dài 0).

Sau quá trình cập nhật, ta có các giá trị đường đi ngắn nhất mới: 

Tiếp theo, ta duyệt đỉnh 5 (đường đi ngắn nhất từ 1 tới 5 có độ dài 1).

Sau cập nhật, ta thu được các giá trị mới:

Tiếp theo, ta duyệt đỉnh 4 (đường đi ngắn nhất từ 1 tới 4 có độ dài 3).

Sau cập nhật, ta thu được các giá trị mới:

Cứ tiếp tục như vậy cho tới khi duyệt hết đỉnh, ta sẽ thu được các giá trị hoàn chỉnh:

Sở dĩ phương pháp tham lam này đúng bởi, ta đã ngầm định đặt ra điều kiện trước: các trọng số của các cạnh phải là các số không âm. Do đó, việc duyệt liên tục từ các đỉnh có độ dài đường đi ngắn nhất là cực tiểu sẽ luôn được đảm bảo tính chính xác: ta không thể xuất phát từ bất kỳ đỉnh nào khác qua một giá trị trung gian mà thu được đường đi nhỏ nhất từ đỉnh gốc tới đỉnh cực tiểu ta đang xét thậm chí còn nhỏ hơn nữa được.

Tuy nhiên, với trường hợp trọng số âm, lập luận này bị bác bỏ. Xét đồ thị sau:

Bằng mắt thường, ta có thể thấy rằng: đường đi ngắn nhất từ đỉnh 1 tới đỉnh 4 sẽ là đoạn đường 1->3->4.

Tuy nhiên, áp dụng tư duy thuật toán Dijkstra, ta có:

• Khởi tạo: s_path[1] = 0, s_path[2] = INF, s_path[3] = INF, s_path[4] = INF.
• Xuất phát từ đỉnh 1. Cập nhật: s_path[2] = 2, s_path[3] = 6.
• Xuất phát từ đỉnh 2. Cập nhật: s_path[4] = 5.
• Xuất phát từ đỉnh 4. Do đây là đỉnh đích nên ngừng thuật toán, kết luận ans = 5.

Rõ ràng, do phương pháp tham lam không tính đến trường hợp độ dài đường đi nhỏ nhất có thể giảm, nên nhánh xuất phát từ đỉnh 3 bị loại bỏ, dẫn đến kết quả sai.

Một phép cài đặt thuật toán Dijkstra thành công được quyết định chủ yếu bởi độ phức tạp của quá trình tìm đỉnh tiếp theo được duyệt.

Với phương pháp khờ khạo, độ phức tạp của quá trình này sẽ là O(V), do đó độ phức tạp của thuật toán trở thành O(V^2).

Ta có thể cải tiến quá trình này thông qua hàng đợi ưu tiên – giúp độ phức tạp của quá trình tìm kiếm đỉnh chỉ biến thiên theo hàm logarithm.

Một ví dụ về việc cài đặt như sau:

Ta nhận thấy, trong cách cài đặt này, trong hàng đợi sẽ chứa độ dài cạnh với giá trị âm. Sở dĩ vậy là bởi, priority_queue của C++ sẽ ngầm định trả về giá trị lớn nhất ở đầu hàng đợi, mà ta lại cần giá trị nhỏ nhất. Tất nhiên, ta có nhiều cách khác để xử lý, như thay đổi toán tử so sánh cho priority_queue, sử dụng STL set/multiset, v.v. …

Độ phức tạp cho cách cài đặt trên là O(E+V*log V).

Bài toán tham khảo: Codeforces 20C – Dijkstra?

Tóm tắt đề bài:

Cho 1 đồ thị vô hướng có trọng số gồm N đỉnh và M cạnh. Hãy tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh N.

Nếu không có đường đi, in ra -1.

Nếu có nhiều đường đi cùng trả về 1 giá trị tối ưu, có thể tùy chọn đường đi.

Phương pháp:

Đây là một bài tập căn bản cho thuật toán Dijkstra. Có một số điểm cần lưu ý:

• Output sẽ trả về -1 nếu sau khi kết thúc duyệt, đường đi ngắn nhất từ 1 tới N là +INF (nhớ rằng đề bài không đảm bảo đồ thị là liên thông).
• Vì ta phải in ra đường đi nên ngoài việc xác định giá trị đường đi nhỏ nhất, ta còn phải thực hiện truy vết. Phương pháp truy vết thì vẫn tương tự như khi duyệt DFS/BFS thông thường.

Lời giải (của D.Bách): Submission 33253245

Một số nội dung được dịch sang tiếng Việt từ sách Competitive Programming’s Handbook của Antti Laaksonen, CSES, Phần Lan.

#ThuyTrang_12A2

Share this:

• Twitter
• Facebook

Like Loading...

Related