Các bài toán về tìm đường đi ngắn nhất và biến tướng của nó luôn xuất hiện rất nhiều trong các cuộc thi lập trình thi đấu bởi sự đa dạng trong cách đưa ra đề bài và sử dụng. Một trong những thuật toán tìm đường đi ngắn nhất được sử dụng phổ biến đó là thuật toán Dijkstra. Show Theo Wikipedia, thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 19561956 và ấn bản năm 19591959, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Thuật toán thường được sử dụng trong định tuyến với một chương trình con trong các thuật toán đồ thị hay trong công nghệ Hệ thống định vị toàn cầu (GPS). Ví dụ: Chúng ta dùng các đỉnh của đồ thị để biểu diễn các thành phố và các cạnh để biểu diễn các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (do đó không âm). Chúng ta cần di chuyển từ thành phố ss đến thành phố tt. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất có thể đi. Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A,B,CA, B, C đường đi A−B−CA-B-C có thể ngắn hơn so với đường đi trực tiếp A−CA-C. Kĩ thuậtMô tả thuật toánĐể dễ hình dung cách hoạt động của thuật toán, ta xét ví dụ sau. Cho đồ thị như hình dưới: Nguồn ảnh: https://www.codingame.com Hãy tìm đường đi ngắn nhất giữa đỉnh CC và các đỉnh còn lại trong đồ thị. Ta sẽ áp dụng thuật toán Dijkstra cho đồ thị trên, hãy nghiên cứu thật kĩ từng công đoạn một vì nếu chỉ bỏ qua một chi tiết nhỏ ta sẽ không thể hiểu thuật toán được:
Chúng ta cũng đánh dấu đỉnh hiện tại đang xét (ban đầu là đỉnh nguồn CC). Ở đồ thị trên, ta đánh dấu bằng một chấm đỏ ở đỉnh CC (đỉnh hiện tại đang xét).
Đỉnh BB đã xong, giờ ta kiểm tra đỉnh kề AA. Ta cộng 00 (giá trị dùng đánh dấu ở đỉnh CC) với 11 (trọng số của cạnh nối đỉnh CC với đỉnh AA) và được 0+1=10 + 1 = 1. Dễ thấy giá trị 11 nhỏ hơn vô cùng (giá trị dùng đánh dấu ở đỉnh AA). Do đó ta sẽ đánh dấu đỉnh AA nhận giá trị 11. Tương tự với đỉnh DD: Yay! Ta đã xét xong các đỉnh kề với đỉnh đang xét (đỉnh CC). Tớ sẽ đánh một dấu tick ở đỉnh CC để thể hiện rằng các đỉnh kề nó đã được xét xong.
Okay, bây giờ ta lặp lại thuật toán như đã làm với đỉnh CC. Chúng ta kiểm tra các đỉnh kề với đỉnh AA (Current node), nhớ rằng không kiểm tra những đỉnh đã xét rồi (đỉnh CC). Vậy là ta chỉ cần kiểm tra đỉnh BB. Với BB, Ta cộng 11 (giá trị được đánh dấu ở đỉnh AA) với 33 (trọng số của cạnh nối đỉnh AA với đỉnh BB) và được 44. Vì 4<74 < 7 nên ta cập nhật giá trị dùng đánh dấu ở đỉnh BB là 44. Sau đó, ta đánh dấu đỉnh AA đã xét xong bằng dấu tick và chọn một đỉnh để xét mới (current node mới) thỏa mãn điều kiện chưa được xét và giá trị đang đánh dấu cho đỉnh đó nhỏ nhất, đó là đỉnh DD.
Done!!! Vậy là tất cả các đỉnh đều đã được xét. Giờ khoảng cách ngắn nhất từ đỉnh CC tới các đỉnh còn lại chính là giá trị đang đánh dấu của đỉnh đó. Ví dụ, từ CC đến BB khoảng cách ngắn nhất là 44, từ CC đến EE khoảng cách ngắn nhất là 55,... Tóm lại thuật toán thực hiện các bước như sau:
Khi đó ta có mã giả cho thuật toán như sau:
Chứng minh thuật toánHiểu cơ bản ý tưởng của thuật toán rồi, nhưng hãy đặt câu hỏi, tại sao thuật toán này hoạt động? Ta sẽ chứng minh tính đúng đắn của thuật toán này. Hãy tham khảo cách chứng minh dưới đây: Định lý: Khi thuật toán Dijkstra kết thúc, dist[v]dist[v] lưu độ dài chính xác đường đi ngắn nhất từ đỉnh ss tới đỉnh vv. Chứng minh: Gọi Ký hiệu SP(s,v)SP(s, v) là độ dài của đường đi ngắn nhất từ ss đến vv trong đồ thị GG. Ta sẽ thực hiện chứng minh bằng phản chứng: Định nghĩa hàm UPDATE()UPDATE() như sau: UPDATE(u,v):dist[v]←min{dist[v],dist[u]+w(u,v)}UPDATE(u, v): dist[v] ← min\{dist[v],dist[u]+w(u, v)\}. Giả sử rằng tồn tại ít nhất một đỉnh vv sao cho dist[v]>SP(s,v)dist[v]> SP(s, v) khi vv được xóa khỏi hàng đợi ưu tiên QQ. Cụ thể, gọi ff là đỉnh đầu tiên được xóa khỏi QQ có tính chất trên. Khi đó, Pf=⟨s=u1,u2,...,uh=f⟩P_f = \langle s = u_1, u_2, ..., u_h = f \rangle là chuỗi các đỉnh trên đường đi ngắn nhất từ ss đến ff, trong đó hh là số đỉnh trên đường đi ngắn nhất này. Xét vòng lặp while mà ta dequeue ff từ QQ. Coi một đỉnh vv được đánh dấu nếu tại thời điểm này vv đã bị xóa khỏi QQ. Gọi uku_k là đỉnh đầu tiên trong PfP_f không được đánh dấu, tức là mọi đỉnh trong đường dẫn con ⟨hs,u2,...,uk−1⟩\langle h_s, u_2, ..., u_{k − 1} \rangle được đánh dấu và do đó đã bị xóa khỏi QQ. Trong phần còn lại của chứng minh, ta sử dụng hai dữ kiện quan trọng sau: Dữ kiện 1: Vì ff là đỉnh đầu tiên bị xóa khỏi QQ nên tại thời điểm loại bỏ nó (ở cuối thuật toán), ta có SP(s,f)<dist[f]SP (s, f) <dist[f], theo đó SP(s,ui)=dist[ui]SP(s, u_i) = dist[u_i] với mọi i<ki <k. Nói cách khác, vì tất cả các đỉnh trong đường dẫn con ⟨hs,u2,...,uk−1⟩\langle h_s, u_2, ..., u_{k − 1} \rangle đã bị xóa khỏi QQ trước ff, mỗi đỉnh này phải được tính đúng các giá trị dist[⋅]dist[·]. Dữ kiện 2: Với bất kỳ 1≤i≤j≤h1 ≤ i ≤ j ≤ h, đường dẫn con ⟨hs,u2,...,uk−1⟩\langle h_s, u_2, ..., u_{k − 1} \rangle của PfP_f phải là đường đi ngắn nhất từ $u_i$ đến uju_j (nếu không, ta có thể thay thế đường dẫn con này trong PfP_f bằng một đường dẫn ngắn hơn và kết quả thu được một đường đi ngắn hơn từ ss đến ff). Sử dụng hai dữ kiện này, ta có hai trường hợp dựa trên giá trị của kk:
dist[uk]≤dist[uk−1]+w(uk−1,uk)dist[u_k] ≤ dist[u_{k−1}] +w(u_{k−1},u_k) (vì ta gọi hàm UPDATE(uk−1,uk)UPDATE(u_{k−1},u_k)) d=SP(s,uk−1)+w(uk−1,uk)d= SP(s,u_{k−1}) +w(u_{k−1},u_k) (sử dụng dữ kiện 1: uk−1u_{k-1} được đánh dấu và k−1<kk−1 < k) \=SP(s,uk)= SP(s,u_k) (dữ kiện 2: ⟨s,...,uk⟩\langle s,...,u_k\rangle là đường đi con của PfP_f) <SP(s,f)< SP(s, f) (vì cạnh có trọng số dương) <dist[f]< dist[f] (giả thiết ban đầu) Ta đã chỉ ra rằng từ bất đẳng thức thứ hai đến bất đẳng thức cuối là sử dụng giả thuyết cạnh có trọng số dương — bởi vì phải có ít nhất một cạnh nữa trong đường đi sau uku_k, đường đi ngắn nhất từ ss đến uku_k phải nhỏ hơn đường đi ngắn nhất từ ss đến ff. Trên thực tế, thuật toán Dijkstra không chính xác khi các cạnh có trọng số âm tồn tại trong đồ thị. Vậy uku_k là một đỉnh vẫn nằm trong QQ, và ta đang dequeue đỉnh ff mặc dù bất đẳng thức trên chỉ ra rằng dist[uk]<dist[f]dist[u_k]<dist[f]. Đây là mâu thuẫn. Vậy điều giả sử sai. Ta có điều phải chứng minh. Cài đặtCode:
Độ phức tạp thời gian O(∣E∣.log∣V∣)O(|E|.log|V|) với ∣E∣|E| là số đỉnh và ∣V∣|V| là số cạnh Ứng dụng thực tế của thuật toán DijkstraMột số ứng dụng của thuật toán Dijkstra trong thực tế:
Tổng kếtVậy trong bài viết vừa rồi, ta đã tìm hiểu các nội dung trong thuật toán Dijkstra. Thuật toán Dijkstra được áp dụng rất nhiều trong các cuộc thi lập trình. Bên cạnh đó, có thêm một số các thuật toán tìm đường đi ngắn nhất khác, chúng ta sẽ bàn luận trong bài viết sau. |