Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số. Trong bài viết này chúng ta cùng tìm hiểu ý tưởng cơ bản của thuật toán Dijkstra. Show Mục lục1. Ý tưởngThuật toán Dijkstra có thể giải quyết bài toán tìm đường đi ngắn nhất trên đồ thị vô hướng lẫn có hướng miễn là trọng số không âm. Ý tưởng cơ bản của thuật toán như sau:
2. Ví dụĐể dễ dàng hiểu ý tưởng của thuật toán. Chúng ta cùng xem ví dụ với đồ thị vô hướng $G$. Thuật toán Dijkstra sẽ tìm khoảng cách từ đỉnh gốc $0$ tới tất cả các đỉnh còn lại trong đồ thị $G$. Đồ thị $G$ Đầu tiên, khởi tạo khoảng cách nhỏ nhất ban đầu tới các đỉnh khác là $+\infty$ và khoảng cách tới đỉnh gốc là 0. Ta được danh sách các khoảng cách tới các đỉnh.
Chọn đỉnh 0 có giá trị nhỏ nhất, xét các đỉnh kề của đỉnh 0: Xét đỉnh 1, khoảng cách từ gốc đến đỉnh 1 là 2.5 < $\infty$ nên ghi nhận giá trị mới là $(2.5, 0)$ (nghĩa là khoảng cách đến đỉnh gốc hiện tại ghi nhận là 2.5, đỉnh kề liền trước là đỉnh 0). Xét tương tự cho đỉnh 2 và 3, ta được dòng thứ 2 trong bảng.
Sau khi xét tất cả các đỉnh ta chọn đỉnh 2 có khoảng cách nhỏ nhất và ghi nhận để xét tiếp. Tiếp tục xét đỉnh kề của 2 là đỉnh 4 và 5 với nguyên tắc nêu ở trên. Xét đỉnh 4, khoảng cách từ đỉnh gốc đến đỉnh 4 sẽ bằng khoảng cách từ đỉnh gốc tới đỉnh 2 cộng khoảng cách từ 2 đến 4. Nghĩa là $2.0+0.6=2.6$ nên ta ghi nhận khoảng cách tại đỉnh 4 là $(2.6, 2)$. Xét tương tự cho đỉnh 5.
Lúc này ta chọn được đỉnh 3 có khoảng cách nhỏ nhất, xét đỉnh kề của đỉnh 3 là đỉnh 5. Khoảng cách từ gốc tới đỉnh 5 $=2.1+2.5=4.6$ lớn hơn khoảng cách hiện tại được ghi nhận, vì vậy giá trị tại đỉnh 5 không đổi.
Đỉnh 1 là đỉnh được chọn tiếp theo, xét đỉnh kề của 1 là đỉnh 4. Khoảng cách từ đỉnh gốc không nhỏ hơn khoảng cách hiện tại nên ta không cập nhật gì ở đỉnh này. Thuật toán Johnson tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong thời gian Với các đồ thị thưa, về mặt tiệm cận nó chạy tốt hơn thuật toán lặp bình phương ma trận hoặc thuật toán Floyd-Warshall. Thuật toán hoặc trả về một ma trận trọng số đường đi ngắn nhất cho tất cả các cặp đỉnh hoặc thông báo đồ thị vào chứa một chu trình trọng số âm. Thuật toán Johnson sử dụng như chương trình con như các thuật toán Dijkstra và thuật toán Bellman-Ford. Thuật toán Johnson sử dụng một kỹ thuật tái trọng số, nó hoạt động như sau. Nếu tất cả các trọng số của cạnh w trong một đồ thị G = (V, E) là không âm, chúng ta có thể tìm các đường đi ngắn nhất giữa tất cả các cặp đỉnh bằng cách chạy thuật toán Dijkstra một lần cho mỗi đỉnh; với hàng đợi ưu tiên nhỏ nhất Fibonaci-heap, thời gian chạy của thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh này là Nếu G có các cạnh trọng số âm nhưng không chứa chu trình với trọng số âm, chúng ta đơn giản tính một tập hợp mới các trọng số cạnh không âm để cho phép chúng ta có thể sử dụng cùng một phương pháp. Tập hợp các trọng số cạnh mới w phải thoả mãn hai tính chất cơ bản. 1. Với tất cả các cặp đỉnh u,vV, một đường đi p là một đường đi ngắn nhất từ u đến v sử dụng hàm trọng số w nếu và chỉ nếu p cũng là một đường đi ngắn nhất từ u đến v sử dụng hàm trọng số w. 2. Với mọi cạnh (u,v), trọng số mới w(u,v) là không âm. Như chúng ta sẽ thấy trong chốc lát, quá trình tiền xử lý G để xác định hàm trọng số mới w có thể được thực hiện trong thời gian O(VE). Đƣờng đi ngắn nhất dành riêng bằng cách tái trọng số Như bổ đề sau đây sẽ chỉ ra, chúng ta có thể dễ dàng đi đến một cách tái trọng số của các cạnh thoả mãn tính chất đầu tiên trên. Chúng ta sử dụng để kí hiệu trọng số đường đi ngắn nhất dẫn được từ hàm trọng số w và kí hiệu cho trọng số đường đi ngắn nhất dẫn được từ hàm trọng số w. ). lg (V2 V VE O ). lg (V2 V VE O Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Bổ đề 3.1 (Tái trọng số không thay đổi đƣờng đi ngắn nhất) Cho một đồ thị định hướng có trọng số G = (V, E) với hàm trọng số w : E R. Đặt h : VR là một hàm bất kì ánh xạ các đỉnh vào các số thực. Với mỗi cạnh (u,v) E, định nghĩa w(u,v) = w(u,v) + h(u) – h(v). Giả sử p = <v0, v1, ..., vk> là một đường đi bất kì từ một đỉnh v0 đến đỉnh vk. Khi đó p là một đường đi ngắn nhất từ v0 đến vk với hàm trọng số w nếu và chỉ nếu có một đường đi ngắn nhất với hàm trọng số w. Nghĩa là w(p) = (v0,vk) nếu và chỉ nếu w(p) = (v0,vk). Cũng như vậy, G có một chu trình trọng số âm sử dụng hàm trọng số w nếu và chỉ nếu G có một chu trình trọng số âm sử dụng hàm trọng số w. Chứng minh Chúng ta bắt đầu bởi w(p) = w(p) + h(v0) – h(vk). Chúng ta có w(p) = 𝑘 w(𝑣𝑖−1, 𝑖=1 𝑣𝑖 ) = 𝑘 𝑤(𝑣𝑖−1, 𝑖=1 𝑣𝑖 ) + ℎ 𝑣𝑖−1 − ℎ(𝑣𝑖)) = 𝑘 𝑤(𝑣𝑖−1, 𝑖=1 𝑣𝑖 ) + ℎ 𝑣0 − ℎ(𝑣𝑘)) (tổng viễn vọng) = w(p) + h(v0) – h(vk). Do vậy, một đường đi bất kì p từ v0 đến vk có w(p) = w(p) + h(v0) – h(vk). Nếu một đường đi từ v0 đến vk ngắn hơn một đường đi khác sử dụng hàm trọng số w, thì nó cũng sẽ ngắn hơn nếu sử dụng trọng số w. Từ đó, w(p) = (v0,vk) nếu và chỉ nếu w(p) = (v0,vk). Cuối cùng, chúng ta chứng minh rằng nếu G có chứa một chu trình trọng số âm sử dụng hàm trọng số w nếu và chỉ nếu nó chứa một chu trình trọng số âm sử dụng hàm trọng số w. Xét một chu trình bất kì c = <v0, v1, ..., vk) trong đó v0 = vk. w(c) = w(c) + h(v0) – h(vk) = w(c). và do vậy c có trọng số âm sử dụng hàm trọng số w nếu và chỉ nếu nó có trọng số âm sử dụng hàm trọng số w. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Xây dựng các trọng số không âm bằng cách tái trọng số Mục tiêu tiếp theo của chúng ta là đảm bảo rằng tính chất thứ 2 cần phải được duy trì: chúng ta muốn w(u,v) không âm cho tất cả các cạnh (u,v) E. Cho trước một đồ thị định hướng có trọng số G = (V,E) với hàm trọng số w : E R, chúng ta tạo một đồ thị mới G’ = (V’, E’) trong đó V’ = V {s} với một đỉnh mới s V và E’ = E {(s,v): v V}. Chúng ta mở rộng hàm trọng số w sao cho w (s,v) = 0 với mọi v V. Chú ý rằng vì s không có cạnh đi vào nó, không có đường đi ngắn nhất trong G’ chứa s khác với các đường đi ngắn nhất với đỉnh nguồn là s. Hơn nữa, G’ không chứa chu trình trọng số âm nếu và chỉ nếu G không chứa chu trình trọng số âm. Hình 3.6(a) minh hoạ đồ thị G’ tương ứng với đồ thị G của hình 3.1. Bây giờ, giả sử G và G’ không có chu trình trọng số âm. Chúng ta định nghĩa h(v) = (s,v) với mọi v V’. Theo bất đẳng thức tam giác (bổ đề 2.10), chúng ta có h(v) h(u) + w(u,v) với mọi cạnh (u,v) E. Do vậy, nếu chúng ta định nghĩa hàm trọng số mới w theo phương trình (3.9), chúng ta có w(u,v) = w(u,v) + h(u) – h(v) 0, và tính chất thứ 2 được thoả mãn. Hình 3.6(b) minh hoạ đồ thị G’ từ hình 3.6(a) với các cạnh được tái trọng số. Tính đƣờng đi ngắn nhất giữa tất cả các cặp đỉnh Thuật toán Johnson để tính đường đi ngắn nhất giữa tất cả các cặp đỉnh sử dụng thuật toán Bellman-Ford (phần 2.1) và thuật toán Dijkstra (phần 2.3) như các chương trình con. Nó giả sử rằng các cạnh được lưu trữ trong các danh sách kề. Thuật toán trả về ma trận |V||V| thông thường D = dij, trong đó dij = (i,j), hoặc nó thông báo đồ thị vào chứa một chu trình trọng số âm. Như bình thường đối với một bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh, chúng ta giả sử các đỉnh được đánh số từ 1 đến |V|. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Hình 3.6 Thuật toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh chạy trên đồ thị trong hình 3.1. (a) Đồ thị G’ với hàm trọng số gốc w. Đỉnh mới s có màu đen. Bên trong mỗi đỉnh ghi h(v) = (s,v). (b) Mỗi cạnh (u,v) được tái trọng số với hàm trọng số w(u,v) = w(u,v) + h(u) – h(v). (c)-(g) Kết quả chạy thuật toán Dijkstra trên từng đỉnh của G sử dụng hàm trọng số w. Trong mỗi phần, đỉnh nguồn u có màu đen, và các cạnh tô đậm là trong cây đường đi ngắn nhất tính được bởi thuật toán. Trong mỗi đỉnh v ghi các giá trị (u,v) và (u,v), phân các nhau bằng một dấu gạch chéo. Giá trị duv = (u,v) bằng (u,v) + h(v) – h(u). JOHNSON(G) 1 Tính G’, trong đó V[G’] = V[G] {s} E[G’] = E[G] {(s,v): v V[G]}, và w(s,v) = 0 với mọi v V[G] 2 if Bellman-Ford(G’,w,s) = FALSE 3 then in “đồ thị vào chứa một chu trình trọng số âm” 4 else for mỗi đỉnh v V[G’] Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 5 do đặt h(v) = (s,v) tính bởi thuật toán Bellman-Ford 6 for mỗi cạnh (u,v) E[G’] 7 dow(u,v) w(u,v) + h(u) – h(v)_ 8 for mỗi đỉnh u V[G] 9 do chạy DIJKSTRA(G, ,u) để tính (u,v) với mọi v V[G] 10 for mỗi đỉnh v V[G] 11 do 12 return D Đoạn mã trên chỉ đơn giản thực hiện các hành động mà chúng ta đã chỉ ra trước đó. Dòng 1 sinh ra G’. Dòng 2 chạy thuật toán Bellman-Ford trên G’ với hàm trọng số w và đỉnh nguồn s. Nếu G’, và do đó G, chứa một chu trình trọng số âm, dòng 3 thông báo điều đó. Các dòng 4-11 giả sử rằng G không chứa các chu trình trọng số âm. Dòng 4-5 đặt h(v) là các giá trị trọng số đường đi ngắn nhất (s,v) tính được bởi thuật toán Bellman-Ford với mọi đỉnh v V’. Dòng 6-7 tính hàm trọng số mới w. Với mỗi cặp đỉnh u,v V, vòng lặp for ở các dòng 8-11 tính trọng số đường đi ngắn nhất (u,v) bằng cách gọi thuật toán Dijkstra một lần cho mỗi đỉnh trong V. Dòng 11 lưu lại ma trận 𝑑𝑢,𝑣 các trọng số đường đi ngắn nhất đúng (u,v), tính được bởi phương trình (3.10). Cuối cùng, dòng 1-2 trả về ma trận D đầy đủ. Hình 3.6 minh hoạ việc thực hiện thuật toán Johnson. Nếu như hàng đợi ưu tiên trong thuật toán Dijkstra được cài đặt dựa trên heap Fibonaci, thời gian chạy của thuật toán Johnson là O(V2lgV + VE). Cài đặt đơn giản hơn là heap nhị phân cho ta một thuật toán chạy trong thời gian O(VElgV), là một thuật toán về mặt tiệm cận chạy nhanh hơn thuật toán Floyd-Warshall nếu đồ thị là thưa. w ) ( ) ( ) , ( , u v h v h u duv Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Chƣơng IV: ỨNG DỤNG THUẬT TOÁN TÌM ĐƢỜNG ĐINGẮN NHẤT VÀO MÔ HÌNH HỆ THỐNG ROUTING TĨNH4.1. Nguyên lý hoạt động cơ bản của Router trong hệ thống mạng. Giao thức định tuyến động không chỉ thực hiện chức năng tự tìm đường và cập nhật bảng định tuyến, nó còn có thể xác định tuyến đường đi tốt nhất thay thế khi tuyến đường đi tốt nhất không thể sử dụng được. Khả năng thích ứng nhanh với sự thay đổi mạng là lợi thế rõ rệt nhất của giao thức định tuyến động so với giao thức định tuyến tĩnh. Yếu tố đầu tiên trong bất cứ quá trình truyền thông nào đó là các thực thể truyền thông phải nói cùng một ngôn ngữ. Đối với các giao thức định tuyến IP cũng vậy, chúng ta có 8 giao thức định tuyến IP động chính có thể chọn lựa; nếu một router sử dụng giao thức RIP và router khác sử dụng giao thức OSPF, chúng không thể chia sẻ thông tin định tuyến vì chúng không nói cùng một loại ngôn ngữ. Chúng ta sẽ cùng tìm hiểu các giao thức định tuyến động còn đang được sử dụng, thậm chí xem xét cách 1 router có thể nói được nhiều loại ngôn ngữ, nhưng trước hết chúng ta cùng khám phá những đặc tính và những vấn đề phát sinh thường gặp nhất đối với các giao thức định tuyến. Cơ bản về giao thức định tuyến Tất cả các giao thức định tuyến động được xây dựng dựa trên giải thuật. Một cách tổng quan, giải thuật là 1 tiến trình (procedure) nhằm giải quyết một vấn đề nào đó. Một giải thuật định tuyến tối thiểu phải xử lý được những tiến trình sau : 1. Tiến trình chuyển thông tin định tuyến cho các router khác 2. Tiến trình nhận thông tin định tuyến từ các router khác 3. Tiến trình xác định tuyến đường tốt nhất dựa trên những thông tin nhận được từ các router khác. 4. Tiến trình để router có thể phản ứng với sự thay đổi của hệ thống mạng. Một số vấn đề thường gặp đối với bất kỳ một giao thức định tuyến nào đó là : quá trình xác định đường đi, metrics, sự hội tụ và khả năng phân tải (load balancing) Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Trên hình là một topo mạng đơn giản với 3 router. Router A nhận ra mạng 192.168.1.0, 192.168.2.0, 192.168.3.0 bởi vì nó có các interfaces nằm trong 3 mạng đó. Router B nhận ra mạng 192.168.3.0, 192.168.4.0, 192.168.5.0 và 192.168.6.0. Router C nhận ra mạng 192.168.6.0, 192.168.7.0, 192.168.1.0. Nhìn lướt qua thì tiến trình chia sẻ thông tin giữa các router có vẻ đơn giản. Chúng ta cùng xem xét Router A: 1. Router A kiểm tra địa chỉ IP và subnetmask tương ứng của nó và phát hiện ra các mạng gắn trực tiếp : 192.168.1.0; 192.168.2.0; 192.168.3.0 2. Router A đưa thông tin về những mạng này và bảng định tuyến của nó, đia kèm theo là một trường Flag dùng để chỉ ra những mạng này là những mạng nối trực tiếp. 3. Router A tạo ra một gói tin với nội dung sau: “Những mạng nối trực tiếp với tôi là 192.168.1.0; 192.168.2.0; 192.168.3.0” 4. Router A truyền thông tin đó, hay còn gọi là bản tin định tuyến cập nhật, tới Router B và Router C 5. Router B và C thực hiện những bước tương tự, gửi bản tin cập nhật về những mạng nối trực tiếp của chúng tới Router A. Router A nhận những thông tin đó và đưa vào bảng định tuyến cùng với địa chỉ của Router đã gửi bản tin đó. Lúc này Router A có thể nhận ra tất cả các subnets trên mạng và địa chỉ của các router mà các subnets đó gắn vào. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Tiến trình này xem ra có vẻ quá đơn giản. Vậy tại sao lại có nhiều giao thức định tuyến và các giao thức định tuyến lại phức tạp như vậy. Chúng ta hãy cùng xem lại ví dụ trên : 1. Sau khi đưa thông tin vào bảng định tuyến, Router A sẽ làm gì tiếp với bản tin cập nhật nó nhận được từ B và C. Ví dụ, liệu Router A có gửi thông tin định tuyến nhận từ B tới C và thông tin định tuyến nhận từ C đến B không ? 2. Nếu Router A không chuyển tiếp thông tin cập nhật như trên, việc chia sẻ thông tin định tuyến có thể không thành công. Ví dụ, nếu kết nối giữa B và C không tồn tại, vậy hai Router này không thể phát hiện ra các subnets của nhau. Do đó, Router A phải chuyển tiếp thông tin cập nhật, nhưng như vậy thì lại tạo ra một cơ số các vấn đề 3. Nếu Router A nhận biết về mạng 192.168.4.0 từ cả B và C, vậy nó sẽ chọn Router nào để đi tới mạng đó. Cả 2 tuyến đường liệu có đúng hay ko ? Tuyến đường nào là tốt nhất 4. Cơ chế nào sẽ được sử dụng để đảm bảo rằng tất cả các router đều có thể nhận được thông tin định tuyến mà không làm cho gói tin định tuyến bị loop trên mạng. Metrics Khi có nhiều tuyến đường để đi đến cùng một mạng đích, Router phải có một cơ chế để tính toán và tìm ra con đường tốt nhất. Metric là một biến số được gán cho các routes, nó có ý nghĩa xếp hạng các routes từ tốt nhất đến dở nhất. Chúng ta quay lại ví dụ trên để giải thích sự cần thiết của Metrics. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Trong bảng định tuyến này, với 4 mạng đích dưới cùng, Router A có thể đi tới chúng thông qua Router B hoặc Router C. Nhưng nếu ví dụ mạng 192.168.7.0 có thể tới thông qua cả B và C, vậy tuyến đường nào là tuyến đường được ưa thích hơn. Các giao thức định tuyến khác nhau sử dụng những loại metric khác nhau. Ví dụ, RIP xác định tuyến đường tốt nhất là một tuyến đường có số lượng hop (router) là ít nhất. EIGRP xác định tuyến đường tốt nhất dựa trên sự kết hợp băng thông và tổng độ trễ của tuyến đường. Các metric được sử dụng : Hop count, bandwidth, load, delay, reliability, cost. Sự hội tụ mạng (convergence) Một đặc tính cực kỳ quan trọng đối với các giao thức định tuyến đó là các thông tin định tuyến trong các bảng định tuyến của tất cả router trong mạng phải cùng chính xác. Nếu Router A trong ví dụ trên xác định tuyến đường tốt nhất đến mạng 192.168.6.0 là qua Router C trong khi đó Router C lại xác định tuyến đường tốt nhất để đến mạng 192.168.6.0 là qua Router A. Khi đó Router A sẽ gửi gói tin có địa chỉ đích 192.168.5.0 tới Router C, Router C liền gửi lại cho Router A, Router A lại gửi cho Router C, và quá trình cứ tiếp diễn như vậy sẽ tạo ra routing loop. Tiến trình đưa tất cả các bảng định tuyến của các router vào một trạng thái đồng nhất và chính xác được gọi là sự hội tụ. Thời gian cần thiết để chia sẻ thông tin qua mạng và để cho tất cả router tính toán tuyến đường tốt nhất của nó được gọi là thời gian hội tụ Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ Ví dụ tiếp theo thể hiện một mạng đã hội tụ, nhưng tại thời điểm to xuất hiện sự thay đổi trong mạng. Kết nối giữa 2 router bên trái bị đứt, 2 router này ngay lập tức |
