THUẬT TÓAN TÌM ĐƯỜNG ĐI NGẮN NHẤT

 

I.1. Thuật tóan bài tóan tìm đường đi ngắn nhất

I.1.1. Mở đầu

Bài toán tìm đường đi ngắn nhất là bài toán quan trọng trong lý thuyết đồ thị, nó được áp dụng để giải quyết rất nhiều bài toán trong thực tế như điều khiển tối ưu, giao thông vận tải, mạng viễn thông ...

Bài toán này có thể chia làm 2 loại:

Tìm đường đi ngắn nhất giữa một cặp đỉnh: Cho đồ thị G(V,E) có trọng số cạnh và hai đỉnh u, v thuộc V tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v trên đồ thị G. Các giải thuật được phát triển để giải bài toán dạng này tiêu biểu là các giải thuật: Dijkstra, Bellman-Ford,...

Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh: Cho đồ thị G(V,E) có trọng số cạnh tìm đường đi từ đỉnh u đến đỉnh v, với mọi cặp đỉnh u, v thuộc V. Các giải thuật đã được phát triển để giải bài toán này là: Floyd-Warshall, Johnson,...

Trong thực tế nhiều khi ta không chỉ cần tìm đường đi ngắn nhất giữa hai đỉnh mà còn cần xác định đường đi ngắn nhất giữa một tập đỉnh này đến một tập đỉnh khác. Bài toán đó được phát biểu như sau: Cho đồ thị G(V,E)có trọng số cạnh và hai tập đỉnh
A,B ÌV tìm đường đi ngắn nhất từ tập đỉnh A đến tập đỉnh B.

I.1.2. Thuật tóan bài tóan tìm đường đi ngắn nhất

Trong bài tóan tìm đường đi ngắn nhất, ta có một đồ thị có trọng số G =(V,E) ; trong đó V: số đỉnh, E : số cạnh; với hàm trọng số w : E àR ánh xạ các cạnh theo các trọng số có giá trị thực.

Trọng số của lộ trình p = < > là tổng của các trọng số cấu thành nên nó.

Ta định nghĩa trọng số của lộ trình đường đi ngắn nhất( shorest - path weight)  từ u đến v theo

nếu có một lộ trình từ u đến v bằng không

 

Như vậy, đường đi ngắn nhất từ đường đi đỉnh u đến đỉnh v được định nghĩa là bất kỳ lộ trình p nào có trọng số w(p) =

Bài tóan đường đi ngắn nhất có các biến thể sau:

+ Tìm đường đi ngắn nhất nguồn đơn : Tìm một lộ trình ngắn nhất từ một đỉnh nguồn sV cho trước đến mọi đỉnh u V.

+ Tìm đường đi ngắn nhất đích đơn : Tìm một lộ trình ngắn nhất từ mọi đỉnh nguồn sV  đến đỉnh u V cho trước. Bằng cách đảo ngược hướng của mỗi cạnh trong đồ thị ta có thể rút gọn bài tóan này  thành nguồn đơn.

+ Tìm đường đi ngắn nhất cặp đơn : Tìm một lộ trình ngắn nhất từ u đến v với các đỉnh u và v đã cho. Nếu giải quyết bài tóan nguồn đơn với mọi đỉnh nguồn u thì cũng giải quyết được bài tóan này.

+ Tìm đường đi ngắn nhất mọi cặp : Tìm một lộ trình ngắn nhất từ u đến v cho mọi cặp đinh (u,v).Có thể giải quyết bài tóan này bằng cách chạy một thuật tóan nguồn đơn từ mỗi đỉnh, nhưng thực tế có thể giải quyết nhanh hơn bằng các thuật tóan như : Floyd-Warshall, Johnson,...

I.1.2.1. Đồ thị có cạnh trọng số âm

Trong một bài bài tóan nguồn đơn, ta có thể có các cạnh mà trọng số của chúng âm. Nếu đồ thị G = (V,E) không chứac các chu trình trọng số âm khả đụng từ nguồn s thì với mọi uV trong số lộ trình ngắn nhất  vẫn được định nghĩa tốt, cho dù có một giá trị âm. Tuy nhiên, nếu có một chu trình trọng số âm khả đụng từ s, các trọng số lộ trình ngắn nhất không được đĩnh nghĩa tốt. Nghĩa là không có một đường đi ngắn nhất nào từ s.

 

 

 

 

 

 

 

 

 

 

 

Hình 1.1. Ảnh hưởngcủa các cạnh có trọng số âm trong đồ thị có hướng

Chỉ có một lộ trình từ s đến a ( lộ trình <s,a>, = w(s,a) = 3). Cũng vậy, chỉ có một lộ trình từ s đến b,  = w(s,a) + w(s,b) = 3 + (-4) = -1. Có rất nhiều lộ trình từ s đến c : <s,c>, <s,c,d,c>, <s,c,d,c,d,c> v.v… Do chu trình <c,d,c> có trọng số 6 +(-3) = 3 >0, nên lộ trình ngắn nhất từ s đến c là <s,c> có trọng số  = 5. Tương tự cũng có nhiều lộ trình từ s đến e : <s,e>, <s,e,f,e>, <s,e,f,e,f,e> v.v… Tuy nhiên, do chu trình <e,f,e> có trọng số 3+ (-6) = -3 <0 nên không có lộ trình ngắn nhất từ s đến e. Do đi qua chu trình trọng số  âm <e,f,e> nhiều lần một cách tùy ý, dẫn đến các lộ trình từ s đến e có trọng số âm lớn tùy ý, do đó = - ∞

 

I.1.2.2.Phép nới lỏng

Hầu hết các bài tóan lộ trình đơn ngắn nhất đều dựa trên một kỹ thuật có tên là phép nới lỏng(relaxaion), một phương pháp ỉam liên tục cận trên trọng số âm lộ trình ngắn nhất thực tế của mỗi đỉnh cho khi cận trên bằng trọng số lộ trình ngắn nhất.

            Với mỗi vV  ta duy trì một thuộc tính d[v] là một cận trên trọng số của một lộ trình ngắn nhất từ nguồn s đến v. Ta gọi d[v] là ước lượng lộ trinh ngắn nhất. Ta khởi tạo các phần tử tiền vị và các ước lượng lộ trình ngắn nhất bằng thủ tục dưới đây:

INIT-SINGLE-SOURCE( G,s)

            For mỗi đỉnh vV

            dod[v]

               

                   

            Sau khi khởi tạo, = NIL với mọi vV , d[v]= 0 với v =s và  d[v]= ∞ với  vV –[s]

            Tiến hành nới lỏng một cạnh (u,v). Ở mỗi bước nới lỏng có thể giảm giá trị của mức ước lượng lộ trình ngắn nhất d[v] và cập nhật lại , mã thực hiện 1 bước nới lỏng  

RELAX(u,v,w)

if d[v] > d[u] +w(u,v)

 then

               

  Hình 1.2 nêu 2 ví dụ về phép nới lỏng một cạnh, một ví dụ ở đó một mức ước lượng lộ trình ngắn nhất giảm và một ví dụ ở đó không có ước lượng nào thay đổi.

 

 

 

 

 

 

 

                                      a                                                                b 

Hình 1.2.Phép nới lỏng của cạnh(u,v)

1.2.a. Do d[v]> d[u]+ w[u,v] trước phép nới lỏng nên giá trị d[v] giảm

1.2.b. d[v]≤ d[u]+ w[u,v]d[v] trước phép nới lỏng nên d[v] không bị phép nới lỏng làm thay đổi

Bổ đề 1.1

Lộ trình con của các lộ trình ngắn nhất là các lộ trình ngắn nhất.

Hệ luận 1.1

Cho G = (V,E) là một đồ thị có hướng với hàm trọng số w:EàR. Giả sử rằng có một lộ trình ngắn nhất p từ một nguồn s đến một đỉnh v có thể phân tích thành s     uàv với một đỉnh u và lộ trình p^’ , thì trọng số của lộ trình ngắn nhất từ s đến v là

Chứng minh

Theo bổ đề trên thì, lộ trình con p^’ là lộ trình ngắn nhất từ nguồn s đến u. Nên

            = w(p)

                        = w(p^’) + w(u,v)

                        = + w(u,v)

Bổ đề 1.2

Cho G = (V,E) là một đồ thị có hướng với hàm trọng số w:EàR và đỉnh nguồn s. Thì với tất cả các cạnh (u,v)E ta có :

            Một số tính chất quan trọng ở phương pháp này

Bổ đề 1.3

Cho G= (V,E) là một đồ thị có hướng với hàm trọng số w:EàR, và cho (u,v) E. Thì sau khi nới lỏng cạnh(u,v) bằng cách thi hành RELAX(u,v,w) ta có d[u] ≤ d[u]+w(u,v)

Bổ đề 1.4

Cho G= (V,E) là một đồ thị có hướng với hàm trọng số w:EàR, và sV  là đỉnh nguồn, và cho đồ thị G khởi tạo bởi INIT-SINGLE-SOURCE( G,s). Thì d[v]≥  với tất cả vV, và bất đẳng thức này được duy trì trên bất kỳ dãy các bước nới lỏng nào trên các cạnh của G. Hơn nữa, một khi d[v] đạt được cận dưới của nó , nó sẽ không bao giờ thay đổi. 

Bổ đề 1.5

Cho G= (V,E) là một đồ thị có hướng với hàm trọng số w:EàR, và sV  là đỉnh nguồn, và cho s   u àv là lộ trình ngắn nhất trong G với vài đỉnh u,v V, và cho đồ thị G khởi tạo bởi INIT-SINGLE-SOURCE( G,s), rồi một dãy các bước nới lỏng gộp lện gọi RELAX(u,v,w) được thi hành trên các cạnh của G.Nếu d[u] = vào bất kỳ lúc nào trước lệnh gọi, thì d[v] = mọi lúc sau lệnh gọi.

Bổ đề 1.6

Cho G= (V,E) là một đồ thị có hướng với hàm trọng số w:EàR, và đỉnh nguồn sV, và mặc nhận rằng G không chứ chu trình trọng số âm khả đụng từ s. Ta hãy gọi INIT-SINGLE-SOURCE( G,s), rồi thi hành bấ kỳ dãy các bước nới lỏng nào trên các cạnh của G tạo ra d[v] = với mọi v V.  Như vậy, đồ thị con phần tử tiền vị G là một cây các lộ trình ngắn nhất có gốc tại s.