Xem mã nguồn của Thuật toán Floyd–Warshall

{{chú thích trong bài}}
Trong [[khoa học máy tính]], '''thuật toán Floyd-Warshall''' (còn được gọi là '''thuật toán Floyd''', '''thuật toán Roy-Warshall''', '''thuật toán Roy-Floyd''' hoặc '''thuật toán WFI''') là một [[thuật toán]] để tìm [[bài toán đường đi ngắn nhất|đường đi ngắn nhất]] trong đồ thị có hướng [[Thuật ngữ lý thuyết đồ thị|đồ thị có trọng số]] với trọng số cạnh dương hoặc âm (nhưng không có chu trình âm).<ref>{{chú thích sách |title=Introduction to algorithms |author=Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford |year=1994 |publisher=MIT press Cambridge, MA, USA}}</ref><ref>{{chú thích sách | author=Kenneth H. Rosen | title=Discrete Mathematics and Its Applications, 5th Edition | publisher = Addison Wesley | year=2003 | isbn=978-0-07-119881-3 }}</ref> Một lần thực hiện thuật toán sẽ tìm ra độ dài (trọng số tổng hợp) của đường đi ngắn nhất giữa mọi cặp đỉnh. Mặc dù nó không trả về chi tiết của các đường đi, có thể khôi phục các đường đi với sửa đổi đơn giản cho thuật toán. Các phiên bản của thuật toán cũng có thể được sử dụng để tìm [[bao đóng chuyển tiếp]] của quan hệ <math>R</math>, hoặc (liên quan đến [[phương pháp bỏ phiếu Schulze]]) [[bài toán đường đi rộng nhất|đường đi rộng nhất]] giữa mọi cặp đỉnh trong đồ thị có trọng số.

==Lịch sử và tên gọi==
Thuật toán Floyd–Warshall là một ví dụ về [[quy hoạch động]], và được xuất bản dưới dạng hiện nay của nó bởi [[Robert W. Floyd|Robert Floyd]] vào năm 1962.<ref>{{chú thích tạp chí | first = Robert W. | last = Floyd | author-link = Robert W. Floyd | title = Algorithm 97: Shortest Path | journal = [[Communications of the ACM]] | volume = 5 | issue = 6 | page = 345 | date=  June 1962 | doi = 10.1145/367766.368168 | s2cid = 2003382 }}</ref> Tuy nhiên, nó về cơ bản giống như các thuật toán trước đó được xuất bản bởi [[Bernard Roy]] vào năm 1959<ref>{{chú thích tạp chí | first = Bernard | last = Roy |author-link=Bernard Roy| title = Transitivité et connexité. | journal = [[C. R. Acad. Sci. Paris]] | volume = 249 | pages = 216–218 | year=  1959 |url=https://gallica.bnf.fr/ark:/12148/bpt6k3201c/f222.image |language=fr }}
</ref> và cũng bởi [[Stephen Warshall]] vào năm 1962<ref>{{chú thích tạp chí | first = Stephen | last = Warshall | title = A theorem on Boolean matrices | journal = [[Journal of the ACM]] | volume = 9 | issue = 1 | pages = 11–12 | date=  January 1962 | doi = 10.1145/321105.321107 | s2cid = 33763989 | doi-access = free }}</ref> để tìm bao đóng chuyển tiếp của một đồ thị,<ref>{{mathworld|id=Floyd-WarshallAlgorithm | title = Thuật toán Floyd-Warshall}}</ref> và có liên quan chặt chẽ với [[thuật toán của Kleene]] (xuất bản vào năm 1956) để chuyển đổi một [[tự động hóa hữu hạn xác định]] thành một [[biểu thức chính quy]].<ref>{{chú thích sách|title=Automata Studies|last=Kleene|first=S. C.|publisher=Princeton University Press|year=1956|editor=[[Claude Elwood Shannon|C. E. Shannon]] và [[John McCarthy (nhà khoa học máy tính)|J. McCarthy]]|pages=3–42|chapter=Representation of events in nerve nets and finite automata|author-link=Stephen Cole Kleene}}</ref> Định dạng hiện đại của thuật toán dưới dạng ba vòng lặp lồng nhau được mô tả đầu tiên bởi Peter Ingerman, cũng vào năm 1962.<ref>{{chú thích tạp chí|last=Ingerman|first=Peter Z.|date=November 1962|title=Algorithm 141: Path Matrix|journal=[[Communications of the ACM]]|volume=5|page=556|doi=10.1145/368996.369016|number=11|s2cid=29010500}}</ref>

==Thuật toán==
Thuật toán Floyd–Warshall so sánh nhiều đường đi khả dĩ trong đồ thị giữa mỗi cặp đỉnh. Nó được đảm bảo để tìm tất cả các đường đi ngắn nhất và có thể làm điều này với <math>\Theta(|V|^3)</math> so sánh trong một đồ thị, mặc dù có thể có <math>\Theta (|V|^2)</math> cạnh trong đồ thị. Nó làm như vậy bằng cách tăng dần ước tính đường đi ngắn nhất giữa hai đỉnh, cho đến khi ước tính tối ưu.

Xét đồ thị <math>G</math> với đỉnh <math>V</math> đánh số từ 1 đến <math>N</math>. Hãy xem xét hàm <math>\mathrm{shortestPath}(i,j,k)</math> trả về độ dài của đường đi ngắn nhất (nếu tồn tại) từ <math>i</math> đến <math>j</math> sử dụng các đỉnh chỉ từ tập <math>\{1,2,\ldots,k\}</math> làm điểm trung gian trong đường đi. Giờ đây, với hàm này, mục tiêu của chúng ta là tìm độ dài của đường đi ngắn nhất từ mỗi <math>i</math> đến từng <math>j</math> sử dụng '''bất kỳ''' đỉnh nào trong <math>\{1,2,\ldots,N\}</math>. Theo định nghĩa, đây là giá trị <math>\mathrm{shortestPath}(i,j,N)</math>, mà chúng ta sẽ tìm [[đệ quy]].

Chú ý rằng <math>\mathrm{shortestPath}(i,j,k)</math> phải nhỏ hơn hoặc bằng <math>\mathrm{shortestPath}(i,j,k-1)</math>: sẽ linh hoạt hơn nếu được phép sử dụng đỉnh <math>k</math>. Nếu <math>\mathrm{shortestPath}(i,j,k)</math> thực sự nhỏ hơn <math>\mathrm{shortestPath}(i,j,k-1)</math>, thì phải có một đường đi từ <math>i</math> đến <math>j</math> sử dụng các đỉnh <math>\{1,2,\ldots,k\}</math> mà ngắn hơn bất kỳ đường đi nào không sử dụng đỉnh <math>k</math>. Đường đi này có thể được phân rã thành:

:(1) một đường đi từ <math>i</math> đến <math>k</math> sử dụng các đỉnh <math>\{1,2,\ldots,k-1\}</math>, kế tiếp là

:(2) một đường đi từ <math>k</math> đến <math>j</math> sử dụng các đỉnh <math>\{1,2,\ldots,k-1\}</math>.

Và dĩ nhiên, chúng phải là các đường đi '''ngắn nhất''' như vậy, nếu không chúng ta có thể làm giảm độ dài hơn nữa. Nói cách khác, chúng ta đã đến công thức đệ quy:
: <math>\mathrm{shortestPath}(i,j,k) =</math>
:: <math>\mathrm{min}\Big(\mathrm{shortestPath}(i,j,k-1),</math>
::: <math>\mathrm{shortestPath}(i,k,k-1)+\mathrm{shortestPath}(k,j,k-1)\Big)</math>.
Trong khi đó, trường hợp cơ sở được đưa ra bởi
: <math>\mathrm{shortestPath}(i,j,0) = w(i,j),</math>
ở đó <math>w(i,j)</math> biểu thị trọng số của cạnh từ <math>i</math> đến <math>j</math> nếu tồn tại và ∞ (vô cùng) trong trường hợp khác.

Các công thức này là trọng tâm của thuật toán Floyd-Warshall. Thuật toán hoạt động bằng cách tính <math>\mathrm{shortestPath}(i,j,k)</math> cho tất cả các cặp <math>(i,j)</math> với <math>k=0</math>, sau đó là <math>k=1</math>, sau đó là <math>k=2</math>, vân vân. Quá trình này tiếp tục cho đến khi <math>k=N</math>, và chúng ta đã tìm thấy đường đi ngắn nhất cho tất cả các cặp <math>(i,j)</math> sử dụng bất kỳ đỉnh trung gian nào. Mã giả cho phiên bản cơ bản này là:

===Mã giả===

 '''cho''' dist là một mảng |V| × |V| của khoảng cách tối thiểu khởi tạo thành ∞ (vô cùng)
 '''đối với mỗi''' cạnh (''u'', ''v'') '''thực hiện'''
     dist[''u''][''v''] &larr; w(''u'', ''v'')  ''// Trọng số của cạnh (''u'', ''v'')''
 '''đối với mỗi''' đỉnh ''v'' '''thực hiện'''
     dist[''v''][''v''] &larr; 0
 '''đối với''' ''k'' '''từ''' 1 '''đến''' |V|
     '''đối với''' ''i'' '''từ''' 1 '''đến''' |V|
         '''đối với''' ''j'' '''từ''' 1 '''đến''' |V|
             '''nếu''' dist[''i''][''j''] > dist[''i''][''k''] + dist[''k''][''j''] 
                 dist[''i''][''j''] &larr; dist[''i''][''k''] + dist[''k''][''j'']
             '''kết thúc nếu'''

==Ví dụ==
Thuật toán trên được thực hiện trên đồ thị ở bên trái trong hình dưới đây:

[[Tập tin:Floyd-Warshall example.svg|600px]]

Trước lần duyệt đệ quy đầu tiên của vòng lặp ngoài, gán {{math|1=''k'' = 0}} ở trên, các đường đi được biết chỉ tương ứng với các cạnh đơn trong đồ thị. Tại {{math|1=''k'' = 1}}, đường đi đi qua đỉnh 1 được tìm thấy: cụ thể là đường đi [2,1,3] được tìm thấy, thay thế đường đi [2,3] có ít cạnh hơn nhưng lại dài hơn (về trọng số). Tại {{math|1=''k'' = 2}}, đường đi đi qua các đỉnh {1,2} được tìm thấy. Các ô màu đỏ và xanh dương cho thấy cách mà đường đi [4,2,1,3] được ghép từ hai đường đi đã biết [4,2] và [2,1,3] gặp trong các lần lặp trước, với 2 trong giao điểm. Đường đi [4,2,3] không được xem xét, vì [2,1,3] là đường đi ngắn nhất gặp từ 2 đến 3. Tại {{math|1=''k'' = 3}}, đường đi qua các đỉnh {1,2,3} được tìm thấy. Cuối cùng, tại {{math|1=''k'' = 4}}, tất cả các đường đi ngắn nhất được tìm thấy.

Ma trận khoảng cách ở mỗi lần lặp của {{mvar|k}}, với các khoảng cách được cập nhật được '''in đậm''', sẽ là:
{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 0}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || 3 || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| &infin; || −1 || &infin; || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 1}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || '''2''' || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| &infin; || −1 || &infin; || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 2}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || 2 || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| '''3''' || −1 || '''1''' || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 3}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || '''0'''
|-
! 2
| 4 || 0 || 2 ||'''4'''
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 4}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || '''−1''' || −2 || 0
|-
! 2
| 4 || 0 || 2 || 4
|-
! 3
| '''5''' || '''1''' || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}
{{clear}}

==So sánh giữa 2 thuật toán dijkstra và Floyd-Warshall==

[[Thuật toán Dijkstra]] bình thường có 2 vòng lặp lồng nhau sẽ có [[Độ phức tạp thuật toán]] là <math>O(n^2)</math>.
Thuật toán Floyd–Warshall bình thường có 3 vòng lặp lồng nhau sẽ có [[Độ phức tạp thuật toán]] là <math>O(n^3)</math>.

{| border="1"
| || <center>'''Dijsktra''' </center> || <center> '''Floyd-Warshall''' </center>
|-
| '''Ưu điểm''' || Chi phí thấp hơn Thuật toán Floyd–Warshall || Không cần chạy lại [[Thuật toán]] (có nghĩa là có tính kế thừa từ đường đi lẫn nhau)
Có thể chạy được với trọng số âm.
|- 
| '''Nhược điểm''' || Không chạy được với [[trọng số]] âm. || Chi phí cao <math>O(n^3)</math> cho mỗi cặp đỉnh

|}

==Chú thích==
{{Tham khảo}}

{{sơ khai}}

[[Thể loại:Bài toán thời gian đa thức]]
[[Thể loại:Giải thuật định tuyến]]
[[Thể loại:Giải thuật lý thuyết đồ thị]]
[[Thể loại:Tối ưu hóa tổ hợp]]
[[Thể loại:Quy hoạch động]]