Kinh nghiệm - Thủ thuật

II.1. Đường đi ngắn nhất với mọi cặp đỉnh

Trở lại bài tóan tìm đường đi ngắn nhất với mọi cặp đỉnh, để giải quyết bài tóan này ta cần chạy một thuật tóan các lộ trình ngắn nhất nguồn đơn  lần, mỗi lần cho một đỉnh làm nguồn. Nếu tất cả các cạnh đều không âm, ta có thể dùng thuật tóan Dijkstra. Nếu thực thi theo mảng tuyến tính của hàng đợi ưu tiên, thời gian thực hiện là O( V³ + VE) = O(V³). Cách thực thi theo đống nhị phân của hành đợi ưu tiên sẽ cho thời gian thực hiện O(VelgV), là một cải thiện nếu đồ thị thưa. Một cách cải thiện khác nếu thực thi theo hàng đơi ưu tiên với đống Fibonaci, mang lại thời gian thực hiện O(V²lgV+VE).

Khi các trọng số không âm, ta không thể thực hiện thuật tóan Dijkstra mà phải chạy thuật tóan Bellman –Ford chậm hơn mỗi lần từ một đỉnh. Thời gian thực hiện kết quả là O(V²E), mà trên đồ thị trù mật nó là O(V²)  

II.2.Các đường đi ngắn nhất và phép nhân ma trận

Khác với bài tóan nguồn đơn, hầu hết các bài tóan ở phần này đều sử dụng một phép biểu diễn ma trận kề. ( Thuật tóan John cho đồ thị thưa sử dụng ma trận danh sách kề). Nhập liệu là một ma trận n x n. W biểu diễn cho trọng số cạnh của một đồ thị

 G = (V,E) có hướng  n. Nghĩa là, đồ thị được biểu diễn một ma trận kề W= (, ở đó

 

	nếu i =j trọng số của cạnh có hướng (i,j)   nếu i ≠ j và i,j E                                                             nếu i ≠ j và i,j  E

 

                                                                                                                     (26.1)(2.1)

 

Trọng số của các cạnh có thể âm, và ta mặc nhiên công nhận đồ thị nhập liệu không chứa chu trình âm.

Giả sử đồ thị được biểu diễn một ma trận kề W= (. Xét một lộ trình ngắn nhất p từ đỉnh i đến đỉnh j, và giả sử p chứa tối đa m cạnh. Giả sử G không có các chu trình trọng số âm, m hữu hạn. Nếu i = j thì p có trọng số 0 và không có các cạnh. Nếu i và j phân biệt ta phân tích lộ trình p thành i   kàj, ở đó p^’ chứa tối đa m-1 cạnh. Hơn nữa, theo bổ đề  trên, p^’ là lộ trình ngắn nhất từ i đến k. Như vậy theo hệ luận 1.2.1 ta có

Giả sử cho  là trọng số cực tiểu của của bất kỳ lộ trình nào từ đỉnh i đến j chứa tối đa m cạnh. Khi m =0, ta có một lộ trình ngắn nhất từ i đến j mà không có các cạnh nếu và chỉ nếu i = j. Như vậy :

 

nếu i = j nếu i ≠ j

               

 

            Với m ≥1 ta tính tóan  dưới dạng cực tiểu của . Như vậy từ định nghĩa theo đệ quy ta có

           

                   =                                                          (2.6.2)(2.2)

Đẳng thức trên đúng với  = 0 với mọi j.

            Đâu là trọng số ngắn nhất thực tế . Nếu đồ thị không chứa các chu trình trọng số âm, thì tất cả các lộ trình ngắn nhất là đơn giản và như vậy chứa tối đa n-1 cạnh. Một lộ trình từ đỉnh i đến j trên n-1 cạnh không thể có ít trọng số hơn một lộ trình ngắn nhất từ i đến j. Do đó, các trọng số lộ trình ngắn nhất thực tế là :

              =                                                    (26.3)(2.3)

Tính tóan các lộ trình ngắn nhất từ dưới lên

Để nhập liệu ta lấy ma trận W= () và tính tóan các ma trận D⁽¹⁾, D⁽²⁾, …D^(n-1), ở đó với m=1,2,…,n-1. Ta có D^(m) = ( ). Ma trận chung cuộc chứa các trọng số của lộ trình ngắn nhất thực tế. Nhận thấy do với tất cả các đỉnh i,j V nên ta có D⁽¹⁾=W. Trọng tâm của thuật tóan là thủ tục dưới đây. Căn cứ vào các ma trận D^(m-1) và W, nó trả về ma trận D^(m) . Nghĩa là nó mở rộng thêm một cạnh cho các lộ trình ngắn nhất đã tính.

EXTEND-SHORTEST –PATHS(D,W)

            n  rows[D]

            cho D^’ = là một ma trận n xn

            for i 1 to n

                        do for j1 to n

                                    do ∞

                                                for k 1 to n

                                                            do  = min(, )

            return D^’

            Ta có thể quan hệ với phép nhân ma trận. Giả sử ta muốn tính tích ma trận C=A*B của 2 ma trận n x n của A và B. Như vậy với i,j= 1,2,…,n ta tính tóan

                                                                                              (26.4)

            Nhận thấy nếu ta tiến hành thay :

           

d^(m-1)  a

            w  b

            d^(m)  c

            min  +

            + .

Trong phương trình (26.2) ta được phương trình (26.4). Như vậy, nếu ta thực hiện thay đổi này với EXTEND-SHORTEST –PATHS và cũng thay ∞ (đồng nhất thức của min) bằng 0( đồng nhất thức của +) ta được thủ tục đơn giản trong phép nhân ma trận.

MATRIX-MULTIPLY(A,B)

n  rows[A]

Cho C là ma trận n x n

for i  1 to n

            do for j  1 to n

                        do    0

                        for  k 1 to n

                                    do    

 return C

Trở lại với bài tóan lộ trình ngắn nhất với mọi cặp, ta tính tóan các lộ trình ngắn nhất bằng cách mở rộng các lộ trình ngắn nhất theo từng cạnh. Việc cho A*B qua kết quả trả về EXTEND-SHORTEST –PATHS(A,B), ta tính dãy n-1 ma trận.

D⁽¹⁾ = D⁽⁰⁾*W = W

D⁽²⁾ = D⁽¹⁾*W = W²

D⁽³⁾ = D⁽¹⁾*W = W³

……………………

D^(n-1) = D^(n-2)*W = W^(n-1)

Thủ tục dưới đây thể hiện dãy tính tóan này

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)

n  rows[W]

D⁽¹⁾ W

for m  2 to n-1

            do D^(m) j  1 to EXTEND-SHORTEST –PATHS(D^(m-1),W)

 return D^(n-1)

Cải thiện thời gian thực hiện

Tuy nhiên, mục tiêu của chúng ta là không tính tóan tất cả các ma trận D^(m) mà chỉ quan tâm đến ma trận D^(n-1) . Với chú ý rằng, không có chu trình trọng số âm thì phương trình (26.3) hàm ý D^(m) = D^(n-1) với tất cả các số nguyên m≥ n-1. Ta có thể tính tóan D^(n-1) với chỉ  tích ma trận bằng cách tính tóan dãy :

D⁽¹⁾ = W        = W

D⁽²⁾ = W²       = W*W

D⁽⁴⁾ = W⁴       = W²*W²

D⁽⁸⁾ = W⁸       = W⁴*W⁴

……………………

D^2(n-1) = W^2(n-2) = W^(n-1)*W^(n-1)

Bởi vì , tích chung cuộc ⁾  sẽ bằng với D^(n-1)

Thủ tục dưới đây tính tóan dãy ma trận trên bằng cách dùng kỹ thuật bình phương lập lại

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)

n  rows[W]

D⁽¹⁾ W

m  2 to n-1

while n-1 > m

            do ⁾  EXTEND-SHORTEST –PATHS(D^(m-1),D^(m))

 return D^(m)

            Trong mỗi lần lặp lại của vòng While, ta tính D^(2m) = (D^(m))^2,  bắt đầu với m =1. Vào cuối mỗi lần lặp ta nhân đôi giá trị m. Lần lặp cuối cùng sẽ tính tóan D^(n-1) bằn thực tế tính tóan D^(2m) với n-1 ≤ 2m ≤ 2n-2. Theo phương trình (26.3) D^(2m) = D^(n-1). Vào lần sau, đợt kiểm tra dòng 4 được thực hiện, ma đã được nhân đôi, do đó giờ đây n-1 ≤m, đợt kiểm tra thất bại và thủ tục trả về ma trận cuối mà nó đã tính tóan.

            Thời gian thực hiện thủ tục FASTER-ALL-PAIRS-SHORTEST-PATHS là (n³lgn), bởi mỗi trong số  tích ma trận mất (n³) thời gian.        

II.3. Thuật toán Floyd – Warshall

Trong đoạn này, ta sẽ dùng một cách trình bày lập trình động khác để giải quyết bài toán các lộ trình ngắn nhất mọi cặp đỉnh trên một đồ thị có hướng G = ( V, E). Thuật toán kết quả, có tên là thuật toán Floyd – Warshall, chạy trong (V³) thời gian. Như trên đây, các trọng số cạnh âm có thể hiện diện, nhưng ta nhận ra không có các chu trình trọng số âm.

 

II.3.1.Cấu trúc của một lộ trình ngắn nhất

            Trong thuật toán Floyd – Warshall, ta dùng một kiểu mô tả đặc điểm khác về cấu trúc của một lộ trình ngắn nhất so với kiểu đã dùng trong các thuật toán mọi cặp gốc phép nhân ma trận. Thuật toán xét các đỉnh trung gian của một lộ trình ngắn nhất, ở đó một đỉnh trung gian của một lộ trình đơn giản p = < v₁, v₂, ..., v_i> là bất kỳ đỉnh nào của p khác ngoài v₁ hoặc v_i, nghĩa là bất kỳ đỉnh nào trong tập hợp {v_2, v₃, ...,v_{i-1 }}

Tất cả các đỉnh trung gian trong {1, 2,...k-1} tất cả các đỉnh trung gian trong {1 ,2, …,k-1} P: tất cả các đỉnh trung gian trong {1, 2,…k}

 

 

 

 

 

 

 

 

Hình 1.3.Lộ trình p là một lộ trình ngắn nhất từ đỉnh i đến đỉnh j, và k là đỉnh trung gian được đánh số cao nhất của p.

Lộ trình p₁, phần lộ trình p từ đỉnh I đến đỉnh k, có tất cả các đỉnh trung gian trong tập hợp {1, 2 , …,k-1} . Điều này cũng áp dụng cho lộ trình p₂ từ đỉnh k đến đỉnh j.

            Thuật toán Floyd – Warshall dựa trên nhận xét dưới đây. Cho các đỉnh của G là V = {1, 2,…n} và xét một tập hợp con {1, 2, …, k} các đỉnh với vài k. Với một cặp đỉnh i, j thuộc V bất kỳ, xét tất cả các lộ trình từ i đến j có tất cả các đỉnh trung gian được rút ra từ {1, 2, …,k} và cho p là một lộ trình trọng số cực tiểu từ trọng số chúng. (Lộ trình p là đơn giản, bởi ta mặc nhận p không chứa các chu trình trọng số âm. Thuật toán Floyd – Warshall khai thác một mối quan hệ giữa lộ trình p và các lộ trình ngắn nhất từ i đến j với tất cả các đỉnh trung gian trong tập hợp {1, 2, …, k-1}. Mối quan hệ tuỳ thuộc vào việc có phải là một đỉnh trung gian của lộ trình p hay không?

            + Nếu k không phải là một đỉnh trung gian của lộ trình p, thì tất cả các đỉnh trung gian của lộ trình p nằm trong tập hợp {1, 2, …,k-1}. Như vậy, một lộ trình ngắn nhất từ đỉnh i đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2,…,k-1} cũng là một lộ trình ngắn nhất từ i đến j với tất cả các đỉnh trung gian trong tập hợp {1, 2,….,k}.

            + Nếu k là một đỉnh trung gian của lộ trình p, thì ta tách nhỏ phần p thành ià p₁à kàp₁à j như đã nêu trong hình 1.1 Theo bổ đề 1.1, p1 là một lộ trình ngắn nhất từ i đến k với tất cả các đỉnh trung gian trong tập hợp {1, 2,…k}. Thực vây, đỉnh k không phải là một đỉnh trung gian của lộ trình p1, và do đó p1 là một lộ trình ngắn nhất từ 1 đến k với tất cả các đỉnh trung gian trong tập hợp {1, 2,…k-1} . Cũng vậy, p₂ là một lộ trình ngắn nhất từ đỉnh k đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2, …k-1}.

II.3.2. Một giải pháp đệ quy cho bài toán các lộ trình ngắn nhất mọi cặp

            Dựa vào các nhận xét trên đây, ta định nghĩa một cách trình bày đệ quy khác về các ước lượng lộ trình ngắn nhất so với trong đoạn II.2. Cho d^(k) _ij là trọng số của một lộ trình ngắn nhất từ đỉnh i đến đỉnh j với tất cả các đỉnh trung gian trong tập hợp {1, 2, ….k}. Khi k = 0, một lộ trình từ đỉnh i đến đỉnh j mà không có đỉnh trung gian nào được đánh số cao hơn 0 sẽ không có các đỉnh trung gian nào cả. Như vậy nó có tối da một cạnh và do đó d⁽⁰⁾ _ij = wij . Một định nghĩa đệ quy dựa vào:

         (26.5)

Ma trận D^(m) = (d^(m) _ij ) cho đáp án chung cuộc d^(m) _ij = δ(i, j) với tất cả i, j thuộc V - bởi tất cả các đỉnh trung gian nằm trong tập hợp {1, 2,….n}.

II.3.3.Thuật tóan Floyd Warshall

            Thuật toán Floyd Warshall áp tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có hướng liên thông có trọng số.

+ Đầu vào : 

- Đồ thị liên thông G =(V,E)

            V ={1,2,….,n} có trọng số với mọi cặp đỉnh (i,j).

            E là tập đỉnh

+ Đầu ra :

  - Ma trận D[d(i,j)], trong đó d(i,j) là chiều dài đường đi ngắn nhất từ i đến j với mọi cặp đỉnh (i,j)

+ Phương pháp

Gồm các bước sau đây :

Bước 1:Khởi tạo ma trận D ( ) là ma trận xuất phát, với :

       -   D0 = [d0(i,j)]

Trong đó :  d0(i,j) =  w(i,j) nếu tồn tại cung (i,j)

                                    +∞ không tồn tại cung (i,j)

Trường hợp đặc biệt không có khuyên tại i thì d0(i,i) = +∞

• P0= [p0(i,j)]

Trong đó :  p0(i,j) =  j nếu có cung đi từ i đến j

                                    Không xác định nếu không tồn tại cung đi từ i đến j

Đầu tiên ta gán k:=0;

Bước 2: Kiếm tra kết thúc dừng

• Nếu k = n thì kết thúc. Lúc đó: D = Dn là ma trận độ dài đường đi ngắn nhất.
• Ngược lại, tăng k lên 1 giá trị (k =k+1),và sang bước 3

Bước 3 - Tinh Bước ma trận  và  theo  và

Với mọi cặp (i,j), i= 1,2,…n, j= 1,2…,n ta thực hiện :

Nếu  đặt :

và

Ngược lại đặt :

và

Quay lại bước 2

Phương pháp xác định đường đi ngắn nhất từ đỉnh I đến j :

Giả sử đường đi ngắn nhất từ I đến j gồm các dãy đỉnh sau :

,

 

6

Thõa mãn :

Ví dụ : Xét đồ thị sau:

 

 

 

 

 

 

 

 

 

 

 

Áp dụng giải thuật Floyd-Warshall ta nhận được các ma trận sau:

- Ma trận xuất phát

 

	a b c d   a   7 5    D0 = b     7 6   c       11   d 4 1		a b c d   a   b c    P0 = b     c d   c       d   d a b

 

 

 

 

 

a b c d   a   7 5    D1 = b     7 6   c       11   d 4 1 9

a b c d   a   b c    P1 = b     c d   c       d   d a b a

- Các ma trận cập nhật qua đỉnh a ( các giá trị mới tô đậm)

 

 

 

 

- Các ma trận cập nhật qua đỉnh b

 

	a b c d   a   7 5 13  D2 = b     7 6   c       11   d 4 1 8 7		a b c d   a   b c b  P2 = b     c d   c       d   d a b b b

 

 

 

 

- Các ma trận cập nhật qua đỉnh c

 

	a b c d   a   7 5 13  D3 = b     7 6   c       11   d 4 1 8 7		a b c d   a   b c b  P3 = b     c d   c       d   d a b b b

 

 

 

 

 

a b c d   a b b c b  P4 = b d d c d   c d d d d   d a b b b

a b c d   a 17 7 5 13  D4 = b 10   7 6   c 15 12 19 11   d 4 1 8 7

- Các ma trận cập nhật qua đỉnh d

- Cuối cùng ta nhận được ma trận khỏang cách giữa các đỉn D = D4. Đồ thị đã cho không chứa chu trình và liên thông.

Chú ý :

Nếu sử dụng ma trận P = P4, ta có thể tìm đường đi ngắn nhất giữa các đỉnh. Ví dụ cần tìm đường đi từ đỉnh c đến d ta thực hiện như sau :

Đặt :               

Từ đó ta nhận được đường đi từ d đến c :

dàbàbàc; với độ dài bằng 7