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 , = 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 : , , v.v… Do chu trình có trọng số 6 +(-3) = 3 >0, nên lộ trình ngắn nhất từ s đến c là có trọng số  = 5. Tương tự cũng có nhiều lộ trình từ s đến e : , , v.v… Tuy nhiên, do chu trình 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 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 giảm 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

            do d[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.

ĐƯỜNG ĐI NGẮN NHẤT VỚI MỌI CẶP ĐỈNH

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

(còn tiếp)